list_map_and_concat
リストの各要素に0要素以上を対応させてつなぎたい時。
(* val list_map_and_concat : ('a -> 'b list) -> 'a list -> 'b list *) let list_map_and_concat f lst = List.rev (List.fold_left (fun a x -> List.rev_append (f x) a ) [] lst )
List.flatten と List.map 使えば書けるけど、どっちも末尾再帰になってないので少しだけ抵抗がある。
少し実験してみた。
let f x = match x mod 4 with | 0 -> [] | 1 -> [x] | 2 -> [x; x+1] | _ -> [x; x+1; x+2] in let lst = let rec iter i result = if i < 0 then result else iter (i-1) (i::result) in iter 100000 [] in (* lst: 0から100000までの整数のリスト *) let t0 = Sys.time () in for i = 0 to 9 do ignore (list_map_and_concat f lst); done; let t1 = Sys.time () in for i = 0 to 9 do ignore (List.flatten(List.map f lst)) done; let t2 = Sys.time () in Printf.printf "%f sec / %f sec\n" (t1 -. t0) (t2 -. t1)
結果、list_map_and_concatが0.922秒、flatten+mapが1.625秒。(ocamlopt, Core Duo 1.83GHz, Windows, Cygwin)
サイズを10倍にするとflatten+mapは落ちました。