F# でCPS版List.foldを作ってみよう

自分用メモ。

まず fold を作る

よく知られる List.fold の定義は、わかりやすいものであれば以下の様な形。

let rec fold' f acc = function
| [] -> acc
| x::xs -> fold' f (f acc x) xs

これをCPS(継続渡しスタイル)に書き換えると

// ('a -> 'b) -> (('a -> 'b) -> 'a -> 'c -> 'b) -> 'a -> 'c list -> 'b
let rec foldk k f acc = function
| [] -> k acc
| x::xs -> f (fun v -> foldk k f v xs) acc x

おそらくこんな感じ。使ってみる。

> foldk id (fun k acc x -> acc + x |> k) 0 [1..5];;
val it : int = 15

> foldk id (fun k acc x -> acc * x |> k) 1 [1..10];;
val it : int = 3628800

一番目の処理を展開してみよう。

foldk id (fun k acc x -> acc + x |> k) 0 [1..5]
(fun k acc x -> acc + x |> k) (fun v -> foldk id (fun k acc x -> acc + x |> k) v [2..5]) 0 1
0 + 1 |> (fun v -> foldk id (fun k acc x -> acc + x |> k) v [2..5])
foldk id (fun k acc x -> acc + x |> k) 1 [2..5]
(fun k acc x -> acc + x |> k) (fun v -> foldk id (fun k acc x -> acc + x |> k) v [3..5]) 1 2
1 + 2 |> (fun v -> foldk id (fun k acc x -> acc + x |> k) v [3..5])
foldk id (fun k acc x -> acc + x |> k) 3 [3..5]
(fun k acc x -> acc + x |> k) (fun v -> foldk id (fun k acc x -> acc + x |> k) v [4..5]) 3 3
3 + 3 |> (fun v -> foldk id (fun k acc x -> acc + x |> k) v [4..5])
foldk id (fun k acc x -> acc + x |> k) 6 [4..5]
(fun k acc x -> acc + x |> k) (fun v -> foldk id (fun k acc x -> acc + x |> k) v [5]) 6 4
6 + 4 |> (fun v -> foldk id (fun k acc x -> acc + x |> k) v [5])
foldk id (fun k acc x -> acc + x |> k) 10 [5]
(fun k acc x -> acc + x |> k) (fun v -> foldk id (fun k acc x -> acc + x |> k) v []) 10 5
10 + 5 |> (fun v -> foldk id (fun k acc x -> acc + x |> k) v [])
foldk id (fun k acc x -> acc + x |> k) 15 []
id 15
15

うん、良い感じ。ただ、継続が最後の引数になるようにしたほうがよいかもしれないと思ったり。

他の関数を定義してみる

簡単な sum から。

let sum k xs = foldk k (fun k x y -> x + y |> k) 0 xs

> sum id [1;2;3];;
val it : int = 6

> sum (~-) [1;2;3];;
val it : int = -6

次に map

let map k f xs = foldk k (fun k xs x -> seq { yield! xs; yield f x } |> Seq.toList |> k) [] xs

> map id ((*) 2) [1..5];;
val it : int list = [2; 4; 6; 8; 10]

続きはまたそのうち。