プログラミングGaucheの19章のコードをHaskellで書き直す

『プログラミングGauche』の19章(継続)のコードをHaskellで書き直す

Gaucheのsyntaxよりも型の明示のあったHaskellの方がスッと理解できるのでmrsekut.icon

関数が純粋である前半の方のものはHaskellで書き直せる

できるだけGaucheのコードを差異がないように書く

ただしprintとかは無視している

型は一般化したものと、具体化したものを書いておく

本書出てくる例に合わせて具体化している

一般化したものはコメントアウトしている

19.2 Schemeによる継続渡しの表現 p.278

継続や継続渡しの概念の関係ないプレーンな実装

末尾再帰ではある

findFold

predで条件を指定できるfold

code:gauche(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))]))

code: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 xs

p. 279

code:gauche(lisp)

(define (process elt seed)

(print "found: " elt)

(cons elt seed))

code:hs

process :: Int -> Int -> Int

process = (:)

find-foldの利用 p.279

code:gauche(lisp)

(find-fold odd? process '() '(1 2 3 4 5 6 7 8 9 10))

code:hs

findFold odd process [] 1..10

-- 9,7,5,3,1

findFoldの引数procをwith contなものにする p.280

findFold2

code: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))]))

code:2.hs

findFold2 :: (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にすべきではあるmrsekut.icon

以下も同様。

findFoldとの相違点

第2引数に取る関数がproc with contに変わっている

これにより、condの第2節が、

「pro」を読んで戻ってきてから、findFoldの再帰をする、から

code:1.hs

| pred x =

let seed2 = pro x seed

in findFold pred pro seed2 xs

procContを呼び出すだけ、に変わっている

code:2.hs

| pred x = procCont x seed $ \seed2 -> findFold2 pred procCont seed2 xs

つまり、第2引数に取る関数(procとprocCont)の呼び方が、継続渡し方式に変わっている

継続を取る版のprocess p.280

process/cont

code:gauche(lisp)

(define (process/cont elt seed cont)

(print "found: " elt)

(cont (cons elt seed)))

code:hs

processCont :: Int -> Int -> (Int -> Int) -> Int

processCont elt seed cont = cont $ elt : seed

processとの相違点

継続渡し方式で関数定義している

利用 p.280

code:hs

findFold2 odd processCont [] 1..10

-- 9,7,5,3,1

挙動は変わらない

breakの例は無理なのでスルー

モナド使って頑張れば出来るとは思うけど

19.3 さらに継続を渡して p.283

findFoldCont

findFold2そのものを継続渡し方式に変えた

code: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)]))

code:hs

findFoldCont :: (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の結果を~)が重要mrsekut.icon

再帰関数は、空リストの場合もそうでない場合も最終的に呼ばれるのは第1節であることを考えると、ここの操作の差異が、「関数の最後の挙動」に影響することがわかる

つまり、findFoldContは、findFold(やfindFold2)と比較して、「関数の最後の挙動」が変わっている

これはCall Stackの話に関わってくる

空リストが渡されたときの挙動に着目するとわかりやすいmrsekut.icon

findFoldの場合は最後の挙動が「seedを返す」なので、findFoldの実行が終わると、呼び出し元に戻ってくる

一方でfindFoldContは最後の挙動が、「contを呼ぶ」なので、findFoldの実行が終わっても、呼び出し元へ返ってこない

その言語が末尾再帰の最適化などをサポートしている場合、こちらのほうが効率が良い

利用 p.283

code:hs

findFoldCont odd processCont [] 1..10 show

-- "9,7,5,3,1"

継続としてshowを渡しているので結果が文字列として返される

call/cc p.285

code:gauche(lisp)

(define (process/cc elt seed)

(call/cc

(lambda (cont)

(print "found: " elt)

(cont (cons elt seed)))))

上の流れをまとめると

https://gyazo.com/e8c2bc2577a6cd8cb735d17c8ad786cc

青丸同士、緑丸同士、赤丸同士は全部同じもの

緑丸と緑線は同等の能力を持つ

一番下の段は、中段の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を使うことで、継続を取ってくることができる

/mrsekut-b/継続わからん

もう少し冗長に書いてる