再帰なら継続渡しで書き直して末尾再帰にできるヨ!!
そんなことを耳にしていたんですが
どうも継続というものが良く分かっていません
まぁ、関数渡すらしいな、程度の認識
再帰といえば fold なわけですが
Haskell だと foldr、OCaml だと List.fold_right です
まぁ、何でもいいんですが
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
とか
let fold_right f lst init = match lst with
| [] -> init
| x::xs -> f x (fold_right f xs init)
とかそういうのです
要するに
fold [] = v
fold (x:xs) = f x (fold xs)
みたいなことになってればいいんです
で、これ末尾再帰にはなってないわけですよ
することに意味があるかは知らないんですよ
したいんですよ、末尾再帰に
できないんですよ、まだ継続とか関数渡すとかの理解浅いから
ぐぐりました
反復的プロセス、末尾再帰、継続渡しスタイル : torus solutions!append が末尾再帰の刑に処せられていますがまぁ fold も同じようなもんです
fold f v [] k = k v
fold f v (x:xs) k = fold f v xs (\y -> k (f x y))
let rec fold f lst v k = match lst with
| [] -> k v
| (x::xs) -> fold f xs v (fun y -> k (f x y))
でもね、
continuation(継続)は末尾再帰の最適化手段ではない : メカAG飽くまで「継続を使うと再帰が末尾再帰に直せる」というだけなので
このままでは「継続」の入口にも立っていないのでした
付録:
で fold には left もありましてこっちは最初から末尾再帰でしたが
(最近 Haskell ご無沙汰なので Haskell だけにしよう、もぉ面倒だ)
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs
こんなだったか
これは例えば
foldl (+) 0 [1,2,3]
= (((0+1)+2)+3)
= (\k -> k.(+1)) ((\k -> k.(+2)) (+3)) 0
= (\x k -> k.(+x)) 1 ((\x k -> k.(+x)) 2 (+3)) 0
= (\x k -> (\y -> k (y+x))) 1 ((\x k -> (\y -> k (y+x))) 2 (\x k -> (\y -> (y+x))) 3 id) 0
= (foldr (\x k -> (\y -> k ((+) y x))) id [1,2,3]) 0
ははは、欺瞞にも程がある
でもまぁ
foldl f v lst = (foldr (\x k -> (\y -> k (f y x))) id lst) v
と書けないこともないということで
何が嬉しいのかは分かりません
