リストに対する操作

整数のリストに含まれる各要素の合計を求める関数を書いてみました。

リストは [0;1;2;3] などとして定義しますが、Haskellのように [0..5] みたいにも書けます。これは [1, 2, 3, 4, 5] と等価です。

再帰を使ってみます。

let arr = [1..10]

let rec sum_rec l s = 
  match l with 
  | [] -> s
  | (h::t) -> s + sum_rec t h
  
let sum l = sum_rec l 0

do printfn "%d" (sum arr)

リストの要素数が少なければ動きますが、[1L..1000000L]のような大きなリストではスタックオーバーフローしてしまいます。末尾最適化されていないのでしょうか。

少し書き直してみました。

let arr = [1L..1000000L]

let add x y = x + y

let rec sum_rec l s = 
  match l with 
  | [] -> s
  | (h::t) -> sum_rec t (add h s)
  
let sum l = sum_rec l 0L

do printfn "%d" (sum arr)

こちらはリストが大きくなっても動作しました。うーん、違いがよくわかりません。要勉強。

ちなみに2つ目のコードは、 List.fold_left を使用することで簡略化できます。

let sum = List.fold_left (fun x y -> x + y) 0L arr

do printfn "%d" sum

やっていることは同じです。

おまけ。List.mapを使用して手続き言語っぽく書いてみました。

let arr = [1L..1000000L]

let mutable sum =  0L
do arr |> List.map (fun x -> sum <- sum + x) |> ignore

do printfn "%d" sum

mutableを使用すると変数への再代入が可能になります。