【関数型言語】Haskell と Scala の畳み込み関数
Scala とHaskell を比較しながら学んでいる。畳み込み関数について、全く違った表記があった。
- Scala では foldLeft ではなく foldRight がスタックオーバーフローの危険がある。
- Haskell では foldr ではなく foldl がスタックオーバーフローの危険がある。
どういうこと？で、ググった。
Scalaの畳み込み関数
、foldLeft は末尾再帰最適化されているのでスタックを消費しないが、（標準の）foldRight は末尾再帰最適化されていないのでスタックを消費してしまう。foldLeftを使って foldRight を実装すると、スタックオーバーフローを回避できる。
Haskellの畳み込み関数
Haskell はデフォルトで遅延評価なので、foldl でもスタックを消費してしまうらしい。
回避するには、正格（遅延評価しない）な関数 foldl' を使う。かと思いきや、Haskell の場合は foldr のほうが計算量が少ない（高速）という記述もあり混乱中。foldr はスタックオーバーフローしないのか？「foldl は無限リストを扱えないが、foldr は無限リストを扱える」らしい。このこととスタックの使い方はどうなっている？
