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