Concurrent Clean : 再帰を繰り返しに

再帰的なプログラムを繰り返し構造に変換するというのは、純粋関数型言語を操る上では（そして、そうでない言語を使う場合にもしばしば）、意外に重要な役割を果たす。というのは、それがある種の「継続」を扱う方法の一つだからだ。
たとえば、次のような再帰的なプログラムを考える。

::Tree a = Tree a [(Tree a)]

showRec (Tree a ts)      f # f = fwrites (toString a) f
                             f = foldl (flip ($)) f $ map showRec ts
                           = f

//テストデータ
l a = Tree a []
t a ts = Tree a ts
data = t 1 [t 2 [l 3, l 4], t 5 [l 6], t 7 [t 8 [l 9], t 10 [l 11]]]

Start w = w --> stdio
            --> \(f,w) = f
            --> fwrites "recursive:"
            --> showRec data
            --> flip fclose w
            --> snd

これは、木構造のデータを表示するシンプルなプログラムだが、このままでは、実行の中断や実行中に別の処理を入れるような変更を加えたい場合、簡単な修正方法がない。
このとき、これを繰り返し構造のプログラムに変更してやると、そのような修正を加えやすい構造のプログラムに変更することができる。
繰り返し構造のプログラムに変更する場合には、２通りの方法があって、１つ目は次のような単純なもの。

showItr []               f = ([], f)
showItr [(Tree a ts):tr] f # f = fwrites (toString a) f
                           = ((ts ++ tr), f) // (tr ++ ts)にすると、幅優先になる

loop [] x = x
loop ts x # (ts, x) = showItr ts x
          = loop ts x

Start w = w --> stdio
            --> \(f,w) = f
            --> fwrites "iterative:"
            --> loop [data]
            --> flip fclose w
            --> snd

このようにすると、最初のプログラムで再帰的に書いていた部分が、loop関数の繰り返し表現に置き換えられる。これによってloop関数の中に、修正を加えるだけで、実行中段や実行中に別の処理を入れるような変更を行うことが可能になる。
しかし、これでは、showItr関数の適用がloop関数の側に残ってしまう。そこで、次のような構造にすると、再帰的な関数の適用もshowItr関数の内側に記述できる。

::F a = E | F (a -> *(F a, a))

showItr []               f = (E, f)
showItr [(Tree a ts):tr] f # f = fwrites (toString a) f
                           = (F (showItr (ts ++ tr)), f)

loop f x # (ff, x) = f x
         = case ff of
             E   = x
             F f = loop f x

Start w = w --> stdio
            --> \(f,w) = f
            --> fwrites "iterative:"
            --> loop (showItr [data])
            --> flip fclose w
            --> snd