Haskellで再帰を心置きなく書いて良い理由（補足編）

• 2022/9/18 「サンク」周りの怪しい言い回しを修正

opaupafz2.hatenablog.com

前回、スタックメモリの観点からもHaskellで再帰をしても良いと言う理由と再帰を書く際に気を付けなければならないことについて書いた。

今回は、その補足として「末尾再帰で書かざるを得ない状況」について書いていこうと思う。

前回では「再帰を書く際は末尾再帰であるかすらどうか気にしなくても良い」と書いたものの、実は末尾再帰で書かなければならないこともある。
たとえば、以下のsum'関数は末尾再帰で書かなければならない。

sum' :: Num a => [a] -> a
sum' [] = 0
sum' (x:xs) = x + sum' xs

なぜ末尾再帰で書かなければならないのかと言うと、sum' [1..]という式を展開してみればわかる。ここで、中置記法ではなくポーランド記法*1で書いてみるとよりわかりやすいだろう。

sum' [1..] = (+) 1 sum' [2..]
           = (+) 1 ((+) 2 sum' [3..])
           = (+) 1 ((+) 2 ((+) 3 sum' [4..]))
           = (+) 1 ((+) 2 ((+) 3 ((+) 4 sum' [5..])))
           = ...

Haskellではすべてが関数である。(+)ですらも関数である。そのため、以上のように部分適用されたままの状態だとHaskellは結果を知ることができないため、サンクがどんどんスタックメモリに格納されていく。

これを末尾再帰で書くと、正格評価にする余地が出てくる。

sum' :: Num a => [a] -> a
sum' (x:xs) = sum'' x xs
    where sum'' :: Num a => a -> [a] -> a
          sum'' acc [] = acc
          sum'' acc (y:ys) = sum'' (acc + y) ys

sum' [1..] = sum'' 1 [2..]
           = sum'' ((+) 1 2) [3..]
           = sum'' ((+) ((+) 1 2) 3) [4..]
           = sum'' ((+) ((+) ((+) 1 2) 3) 4) [5..]
           = ...

この時点ではまだ遅延評価によってsum''関数の再帰を終えるまで四則演算の評価が先延ばしにされるため、seq関数または($!)関数を使う。

sum' :: Num a => [a] -> a
sum' (x:xs) = sum'' x xs
    where sum'' :: Num a => a -> [a] -> a
          sum'' acc [] = acc
          sum'' acc (y:ys) = (sum'' $! (acc + y)) ys

sum' [1..] = sum'' 1 [2..]
           = sum'' ((+) 1 2) [3..]
           = sum'' 3 [3..]
           = sum'' ((+) 3 3) [4..]
           = sum'' 6 [4..]
           = sum'' ((+) 6 4) [5..]
           = sum'' 10 [5..]
           = ...

以上からわかることは、遅延評価の仕組みを以てしてもスタックオーバーフローが起こる場合、正格評価にするのと同時に、再帰は末尾再帰で書かなければならないと言うことである。