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]
続きはまたそのうち。