Haskell は遅延評価のために式を展開して計算しないままサンクとしてスタックに保持しています。
下のfoldl (+) 0 (1:2:3:[])を正格評価すれば(0 + 1)の結果である1を保持するのですがそうはしません。
foldl (+) 0 (1:2:3:[]) == foldl (+) (0 + 1) (2:3:[]) == foldl (+) ((0 + 1) + 2) (3:[]) == foldl (+) (((0 + 1) + 2) + 3) [] == (((0 + 1) + 2) + 3)
そうすると大きなリストを処理するときはスタックの消費が大きくなります。
1から1000000までの合計をfoldlで求めると1000000では計算できますが、10000000だとスタックがオーバーフローを起こしてしまいます。
Prelude > foldl (+) 0 [1..1000000] 500000500000
しかし、foldl' を使えば正格評価を行うのでオーバーフローを起こしません。
Prelude> :m + Data.List Prelude Data.List> foldl' (+) 0 [1..10000000] 50000005000000 Prelude Data.List> foldl' (+) 0 [1..100000000] 5000000050000000
正格評価を行うためには、２つの引数を取り、最初の引数を評価して捨て、２番目の引数の評価結果を返すseq という関数が使われています。
Prelude> :m + Debug.Trace Prelude Debug.Trace> seq (trace "1+2" 1+2) 3+4 1+2 7
seq を使った foldl'
import Debug.Trace {- foldl' _ zero [] = zero foldl' step zero (x:xs) = let new = step zero x in new `seq` foldl' step new xs -} foldl' _ zero [] = zero foldl' step zero (x:xs) = let new = trace("new = ((+)"++ show zero ++" "++ show x++")") (step zero x) in trace(show new ++" `seq` foldl' (+) "++show new++" "++show xs) (new `seq` foldl' step new xs)
((+)1 1)、((+)2 2)、((+)4 3) とサンクとして式が保持されないで計算結果が次の再帰に渡されていきます。
Main> foldl' (+) 1 [1..10] new = ((+)1 1) 2 `seq` foldl' (+) 2 [2,3,4,5,6,7,8,9,10] new = ((+)2 2) 4 `seq` foldl' (+) 4 [3,4,5,6,7,8,9,10] new = ((+)4 3) 7 `seq` foldl' (+) 7 [4,5,6,7,8,9,10] new = ((+)7 4) 11 `seq` foldl' (+) 11 [5,6,7,8,9,10] new = ((+)11 5) 16 `seq` foldl' (+) 16 [6,7,8,9,10] new = ((+)16 6) 22 `seq` foldl' (+) 22 [7,8,9,10] new = ((+)22 7) 29 `seq` foldl' (+) 29 [8,9,10] new = ((+)29 8) 37 `seq` foldl' (+) 37 [9,10] new = ((+)37 9) 46 `seq` foldl' (+) 46 [10] new = ((+)46 10) 56 `seq` foldl' (+) 56 [] 56
