末尾再帰とcontinuation passing style

文字列を逆順にする関数reverseは以下のとおり

reverse [] = []
reverse (h:t) = (reverse t) ++ [h]

空のときは逆順も空、何かあるときは、全体を頭と残りにわけ、残り側を逆順にしたものの後ろに頭を付け足す。

これは末尾再帰ではない。なぜなら内側のreverse呼び出し後にさらに処理(append関数の呼び出し)を行っているから。一般的に末尾再帰にする理由は、末尾再帰呼び出しの場合、処理系がその処理を高速化するから

reverse [] = []
reverse (h:t) = let rt = reverse t in
                (++) rt [h]

reverseを末尾再帰にしたバージョンは以下のようになる。

reverse l = reverseIn l []
  where
    reverseIn [] acc = acc
    reverseIn (h:t) acc = let nacc = h:acc in
                          reverseIn t nacc

reverseに"abc"を渡したコールイメージは、以下のとおり

reverseIn "abc" []
  reverseIn "bc" 'a':[]
    reverseIn "c" 'b':"a"
      reverseIn [] 'c':"ba" --> "cba"

この末尾再帰呼び出しに変えるために追加した引数をアキュムレータと呼んだりする。
末尾再帰呼び出しにすると高速化できるのは以下の理由から

• 後処理をせず大本の呼び出しまで一気に処理を戻せる
• 再帰の関数呼び出しでは、新たに関数フレームを作らずに、呼び出し元関数のフレームを上書きして使いまわせる

ただし、再帰関数を末尾再帰関数呼び出しにするのは普通は知恵がいる。このreverseのようなアキュムレータ操作を思いつくのは普通は難しい。そこで再帰呼び出しの後の処理を関数にして、それを渡し最後に実行してみよう。

reverse (h:t) = reverse t (\rt -> rt ++ [h])

これは引数の数が違うので正しくない。そこで引数nextを追加する。このnextにあたる内側の(\rt -> rt ++ t)はreverse tした結果を受け取る必要がある。そのため、nextは外側のreverse計算の結果である、rt ++ hを引数にとるとになる。

reverse (h:t) next = reverse t (\rt -> next (rt ++ [h]))

同様に空の場合もnextを引数にもち、nextはreverseの結果である空リストを受け取る。

reverse [] next = next []
reverse (h:t) next = reverse t (\rt -> next (rt ++ [h]))

大本で実行する場合は、next result = resultを返せばいいため、同様の定義となるid関数を渡してやる。

reverse "abc" id
  reverse "bc" (\rt1 -> id (rt1 ++ "a"))
    reverse "c" (\rt2 -> (\rt1 -> id (rt1 ++ "a")) (rt2 ++ "b"))
      reverse [] (\rt3 -> (\rt2 -> (\rt1 -> id (rt1 ++ "a")) (rt2 ++ "b")) (rt3 ++ "c"))
        (\rt3 -> (\rt2 -> (\rt1 -> id (rt1 ++ "a")) (rt2 ++ "b")) (rt3 ++ "c")) []
          (\rt2 -> (\rt1 -> id (rt1 ++ "a")) (rt2 ++ "b")) ([] ++ "c")
             (\rt1 -> id (rt1 ++ "a")) (([] ++ "c") ++ "b")
               id ((([] ++ "c") ++ "b") ++ "a"))
                 ((([] ++ "c") ++ "b") ++ "a")) -- "cba"