プログラミングGaucheの19章のコードをHaskellで書き直す
『プログラミングGauche』の19章(継続)のコードをHaskellで書き直す
Gaucheのsyntaxよりも型の明示のあったHaskellの方がスッと理解できるので
関数が純粋である前半の方のものはHaskellで書き直せる
できるだけGaucheのコードを差異がないように書く
ただしprintとかは無視している
型は一般化したものと、具体化したものを書いておく
本書出てくる例に合わせて具体化している
一般化したものはコメントアウトしている
>19.2 Schemeによる継続渡しの表現 p.278
継続や継続渡しの概念の関係ないプレーンな実装
末尾再帰ではある
findFold pred で条件を指定できるfoldgauche(lisp)(define (find-fold pred? proc seed lis)
(cond [(null? lis) seed]
[(pred? (car lis))
(let ((seed2 (proc (car lis) seed)))
(find-fold pred? proc seed2 (cdr lis)))]
[else
(find-fold pred? proc seed (cdr lis))]))1.hs-- findFold :: (t1 -> Bool) -> (t1 -> t2 -> t2) -> t2 -> [t1] -> t2
findFold :: (Int -> Bool) -> (Int -> [Int] -> [Int]) -> [Int] -> [Int] -> [Int]
findFold pred pro seed [] = seed
findFold pred pro seed (x:xs)
| pred x =
let seed2 = pro x seed
in findFold pred pro seed2 xs
| otherwise = findFold pred pro seed xsp. 279
gauche(lisp)(define (process elt seed)
(print "found: " elt)
(cons elt seed))hsprocess :: Int -> [Int] -> [Int]
process = (:)find-foldの利用 p.279
gauche(lisp)(find-fold odd? process '() '(1 2 3 4 5 6 7 8 9 10))hsfindFold odd process [] [1..10]
-- [9,7,5,3,1]>findFoldの引数procをwith contなものにする p.280
findFold2 gauche(lisp)(define (find-fold2 pred? proc/cont seed lis)
(cond [(null? lis) seed]
[(pred? (car lis))
(proc/cont (car lis)
seed
(lambda (seed2)
(find-fold2 pred? proc/cont seed2 (cdr lis))))]
[else
(find-fold2 pred? proc/cont seed (cdr lis))]))2.hsfindFold2 :: (Int -> Bool) -> (Int -> [Int] -> ([Int] -> [Int]) -> [Int]) -> [Int] -> [Int] -> [Int]
findFold2 pred procCont seed [] = seed
findFold2 pred procCont seed (x:xs)
| pred x = procCont x seed $ \seed2 -> findFold2 pred procCont seed2 xs
| otherwise = findFold2 pred procCont seed xs本来の意味での命名は
procCont ではなく procWithCont にすべきではある以下も同様。
findFold との相違点第2引数に取る関数が
proc with cont に変わっているこれにより、
cond の第2節が、「pro」を読んで戻ってきてから、
findFold の再帰をする、から1.hs | pred x =
let seed2 = pro x seed
in findFold pred pro seed2 xsprocContを呼び出すだけ、に変わっている
2.hs| pred x = procCont x seed $ \seed2 -> findFold2 pred procCont seed2 xsつまり、第2引数に取る関数(
proc と procCont )の呼び方が、継続渡し方式に変わっている継続を取る版のprocess p.280
process/cont gauche(lisp)(define (process/cont elt seed cont)
(print "found: " elt)
(cont (cons elt seed)))hsprocessCont :: Int -> [Int] -> ([Int] -> [Int]) -> [Int]
processCont elt seed cont = cont $ elt : seed process との相違点継続渡し方式で関数定義している
利用 p.280
hsfindFold2 odd processCont [] [1..10]
-- [9,7,5,3,1]挙動は変わらない
break の例は無理なのでスルーモナド使って頑張れば出来るとは思うけど
>19.3 さらに継続を渡して p.283
findFoldCont findFold2 そのものを継続渡し方式に変えたgauche(lisp)(define (find-fold/cont pred? proc/cont seed lis cont)
(cond [(null? lis) (cont seed)]
[(pred? (car lis))
(proc/cont (car lis)
seed
(lambda (seed2)
(find-fold/cont pred? proc/cont seed2 (cdr lis) cont)))]
[else
(find-fold/cont pred? proc/cont seed (cdr lis) cont)])) hsfindFoldCont :: (Int -> Bool) -> (Int -> [Int] -> ([Int] -> [Int]) -> [Int]) -> [Int] -> [Int] -> ([Int] -> [Int]) -> [Int]
findFoldCont pred procCont seed [] cont = cont seed
findFoldCont pred procCont seed (x:xs) cont
| pred x = procCont x seed $ \seed2 -> findFoldCont pred procCont seed2 xs cont
| otherwise = findFoldCont pred procCont seed xs cont findFold2 との相違点condの1節が
cont の結果を返しているcondの2,3節で再帰するときに
cont も渡しているこれの前者の方(1節が
cont の結果を~)が重要再帰関数は、空リストの場合もそうでない場合も最終的に呼ばれるのは第1節であることを考えると、ここの操作の差異が、「関数の最後の挙動」に影響することがわかる
つまり、
findFoldCont は、 findFold (や findFold2 )と比較して、「関数の最後の挙動」が変わっているこれはCall Stackの話に関わってくる
空リストが渡されたときの挙動に着目するとわかりやすい
findFold の場合は最後の挙動が「 seed を返す」なので、 findFold の実行が終わると、呼び出し元に戻ってくる一方で
findFoldCont は最後の挙動が、「 cont を呼ぶ」なので、 findFold の実行が終わっても、呼び出し元へ返ってこないその言語が末尾再帰の最適化などをサポートしている場合、こちらのほうが効率が良い
利用 p.283
hsfindFoldCont odd processCont [] [1..10] show
-- "[9,7,5,3,1]"継続として
show を渡しているので結果が文字列として返される>call/cc p.285
gauche(lisp)(define (process/cc elt seed)
(call/cc
(lambda (cont)
(print "found: " elt)
(cont (cons elt seed)))))>
上の流れをまとめると
青丸同士、緑丸同士、赤丸同士は全部同じもの
緑丸と緑線は同等の能力を持つ
一番下の段は、中段の
process の引数を表している find-fold 内で、継続付き process を使うためには、「
find-fold の引数部分」あるいは「 find-fold 全体」を継続渡しに変更する必要がある前者が
find-fold2 で、後者が find-fold/cont に相当するなぜなら
process 側の引数の個数が変わっているから。 process/cont は cont という引数を追加で取っているただ、この書き換えは微妙にダルい
何とかして、
find-fold のまま、継続あり process を使いたいそこで
call/cc が役に立つ find-fold はそのままに、 process のみを書き換えることで実現できる process と process/cc は同じく2引数なので、 find-fold へ適用することが出来る process/cc 内では継続を使うが、引数でからはもらってきていない call/cc を使うことで、継続を取ってくることができるもう少し冗長に書いてる