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は落ちました。