「Real World Haskell」読書メモ 4.関数プログラミング 4.6 ループをどのように考えるか

Real World Haskell　4.関数プログラミング 4.6 ループをどのように考えるか
末尾再帰が何がそんなに騒ぐほどのことなのか
関数型言語はループがないので再帰関数を使用しますが、再帰適用ごとにメモリを割り当てるのは明らかに不利。
関数型言語では末尾再帰が使われているかどうかを検出し、末尾再帰最適化（TCO）を行なう。

-- フィボナッチ数を再帰で求める
fibo 0 = 1
fibo 1 = 1
fibo n = fibo (n - 1) + fibo (n - 2)

main = putStrLn $ show $ fibo 30

./recursion +RTS -s
recursion.exe +RTS -s
1346269
     151,314,228 bytes allocated in the heap
         119,308 bytes copied during GC
           3,096 bytes maximum residency (1 sample(s))
          16,064 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:   288 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.27s  (  0.27s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.27s  (  0.27s elapsed)

  %GC time       0.0%  (0.7% elapsed)

  Alloc rate    569,653,564 bytes per MUT second

  Productivity 100.0% of total user, 97.8% of total elapsed

-- フィボナッチ数を末尾再帰で求める
fibo  n     = fibo' n 1 0
fibo' 0 a _ = a
fibo' n a b = fibo' (n - 1) (a + b) a

main = putStrLn $ show $ fibo 30

./tailCall +RTS -s
tailCall.exe +RTS -s
1346269
           8,712 bytes allocated in the heap
             348 bytes copied during GC
           1,452 bytes maximum residency (1 sample(s))
          10,836 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:     0 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.02s  (  0.00s elapsed)
  MUT   time    0.00s  (  0.00s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.02s  (  0.00s elapsed)

  %GC time       0.0%  (0.0% elapsed)

  Alloc rate    557,568 bytes per MUT second

  Productivity   0.0% of total user, 0.0% of total elapsed

フィボナッチは二重再帰なので呼ばれるごとに二ヶ所で再帰するので1,2,4,8,16と爆発的に再帰する。
1 から N までの和を求める方法ではさほどの差はなかった。
+RTS -s オプションでheapやらが出力されますが、意味はよく分ってません。数字が大きいのはなにかいっぱいメモリを使ったり、GCしているっぽい。