限定継続でmap関数をひっくり返す

Haskell

前回の例はちょっと意味不明だった。単にshiftをmap関数に渡してみたかったのだけど…

もっとわかりやすく、shift/reset を使って map 関数をひっくり返したものを作ってみた。
が、やっぱりモナドなので普通のSchemeの例より読みにくいような気もする。

まあしかし、shift/reset の型付けを理解するのに良い例のような気もするので、そのまま載せちゃいます

-- 再帰的な限定継続を保持する型
data Iter = 
    Iter (Int -> C [Int] [Int] Iter, Int) -- 限定継続と，何か整数を保持 
  | End [Int] -- おわり

-- ひっくり返されたmap関数
pam []     = ret []
pam (x:xs) = shift (\k -> ret $ Iter (k, x)) >== \y -> pam xs >== \ys -> ret (y:ys)

使ってみる。

expr = reset (pam [1,2,3] >== \xs -> ret (End xs))

ここで reset の前に リストの結果を End に格納しているのに注目。
shiftのanswer type ( \k -> e の e の型) とresetの型は一致させる必要がある。 Iter 型は限定継続を格納する型だが、shiftが消費され尽くした後は、計算結果がほしい。 End はそんな「計算結果」を格納するのに使う。

expr の結果を取り出すには、run expr とする。 run expr した結果、型 Iter が返ってくる。 Iter型に格納されている継続を呼び出して、返ってきたIter型の継続を更に呼び出す… 関数 iter を次の通り定義する。

iter :: (Int -> Int) -> Iter -> [Int]
iter f (Iter (k,x))  = run (k (f x) >== \it -> ret (iter f it))
iter _ (End xs)      = xs

run expr した結果返ってくるIter型(限定継続)を iter でぶん回せば、 ひっくり返されたmap関数が実行できる．

main = mapM_ print [iter id $ run expr, iter (*10) $ run expr]

ideoneに貼付けてみた。

[1,2,3]
[10,20,30]

あえて型シグネチャを書かなかったけど、 expr :: C a a Iter, pam :: [Int] -> C Iter Iter [Int] である。 C a a b の 型 a に、shiftに渡す式のアンサータイプを書く感じだろうか??