手動でCPS変換の練習
命名規則
継続は
cont で表す f という名前の関数をCPSにしたときの関数名は fc とする1引数の単純な関数
Q.
hsf x = x + 1A.
hsfc x cont = cont $ x + 11引数で内部で関数を呼ぶ
Q.
hsg :: Int -> Int
g = undefined
f x = g x + 1 g もCPSに変えることA.
hsfc x cont = cont $ gc x $ \y -> y + 1内部で2つの関数を呼ぶ
Q.
hsh a b = f a + g b h , f , g をCPSにするA.
hshc a b cont = cont $ fc a $ \x -> gc b $ \y -> x + y考え方としては、
f と g を1つずつ継続渡しにしていくと良い気がするまず
h と f を継続渡しにし、 g はそのままとして変換してみるhshc a b cont = cont $ fc a $ \x -> x + g bわかりにくければ
g b をなにか大きなひとかたまり ♠ とみなせばいいhsh a b = f a + ♠ -- もともと
hc a b cont = cont $ f a $ \x -> x + ♠ -- 継続渡し次に、
g も継続渡しに変えるhshc a b cont = cont $ fc a $ \x -> gc b $ \y -> x + yこんなふうに改行すると演算している順序がわかりやすい
hshc a b cont = cont $
fc a $ \x ->
gc b $ \y ->
x + y手続き的言語でこう書いているのと同じように見れる
jsconst h = (a, b) => {
const aa = f(a);
const bb = g(b);
return aa + bb;
}まず
f a を計算して、次に g b を計算して、最後にそれらを足し合わせる、というのを順序を明示して書いている感じになっているたぶん本当は
(+) もCPSにしないといけない単純な再帰関数
階乗fact
Q.
hsfact n
| n == 0 = 1
| otherwise = n * fact(n-1)A.
hsfactc n cont
| n == 0 = cont 1
| otherwise = factc (n-1) $ \x -> cont $ n * x n==0 のときは、ただたんに結果を cont に適用すればいいので簡単 otherwise のときも、ちゃんと「演算の順序」に着目すればいいまず最初に
fact(n-1) が行われて、その後に
n * その結果 の演算が行われると、考えれて、いったん
cont の適用を無視すれば otherwise = factc (n-1) $ \x -> n * x とかけることがわかる cont は「最終的な演算結果」に適用されれば良いここでの最終的な演算結果は
n * x の部分になるのでここに適用して、
cont $ n * x 自動的にこれは末尾再帰になる
計算の過程を逐次的に書いてみると
aaaafactc 3 id
=> factc 2 $ \x -> id $ 3 * x
=> factc 1 $ \y -> (\x -> id $ 3 * x) $ 2 * y
=> factc 0 $ \z -> (\y -> (\x -> id $ 3 * x) $ 2 * y) $ 1 * z
=> (\z -> (\y -> (\x -> id $ 3 * x) $ 2 * y) $ 1 * z) 1
=> (\y -> (\x -> id $ 3 * x) $ 2 * y ) $ 1 * 1
=> (\x -> id $ 3 * x) $ 2 * 1
=> id $ 3 * 2
=> 62回呼ぶ再帰関数
フィボナッチfib
「内部で2つの関数を呼ぶ」と「単純な再帰関数」の組み合わせ
Q.
hsfib n
| n == 0 = 0
| n == 1 = 1
| otherwise = fib (n-1) + fib (n-2)A.
hsfibc n cont
| n == 0 = cont 0
| n == 1 = cont 1
| otherwise =
fibc (n-1) $ \x ->
fibc (n-2) $ \y ->
cont $ x + y otherwise の部分は上の考え方と同じようにやればできる fib (n-2) を塊 ♠ として、 cont も無視する otherwise = fibc (n-1) $ \x -> x + ♠ ♠ も展開する otherwise = fibc (n-1) $ \x -> fib (n-2) \y -> x + y 最終的な演算結果を`contに適用する
otherwise = fibc (n-1) $ \x -> fib (n-2) \y -> cont $ x + y 自動的に末尾再帰になる
引数に取る関数も含めてCPSに変換数
Q.
hsfindFold :: (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 xshs findFoldc :: (Int -> Bool) -> (Int -> [Int] -> ([Int] -> [Int]) -> [Int]) -> [Int] -> [Int] -> ([Int] -> [Int]) -> [Int]
findFoldc pred procCont seed [] cont = cont seed
findFoldc pred procCont seed (x:xs) cont
| pred x = procCont x seed $ \seed2 -> findFoldc pred procCont seed2 xs cont
| otherwise = findFoldc pred procCont seed xs cont