Haskellのfoldlとfoldr、その決定的な違い

Differences Between `Foldl` and `Foldr`

Haskellのfoldlとfoldr、その決定的な違い

Haskellのfoldlとfoldrは、単に「左から」と「右から」の違いではない。結合性の違いが評価順序に影響し、遅延評価ではfoldlがサンクを積み上げてメモリを浪費する一方、foldrは無限リストを扱えるなど、実用的な差が生まれる。厳密な蓄積関数にはfoldl'を、遅延な第二引数にはfoldrを使うのが定石だ。

foldrは無限リストを操作できるが、foldlにはそれができない。
  1. s-zeng

    リストに対するfoldrの、foldlにはない素晴らしい点は、各foldステップで制御フローを完全に蓄積関数に委ねるということだ。つまり、foldrを使えば、foldl'や途中で抜けるリスト走査など、リストの任意の走査を実装できる。https://github.com/quchen/articles/blob/master/useful_techni... を参照。

  2. layer8

    > foldlもfoldrも構造を同じ順序で走査する。リストの場合、それは左から右を意味する。

    この説明は議論の余地がある。単方向連結リストを前提とするなら別だが、単方向連結リストは定義上左から右にしか走査できない(ましてやリストの長さが不定になり得る遅延言語ではなおさらだ)。配列や双方向連結リスト上で正格言語で実装した場合、foldrの走査順序は右から左になる。

    より正確に言えば、Haskellではリストは左から右にしか走査できず、したがってHaskellにおけるfoldlとfoldrの実装は必然的にそれに基づいている、ということだ。

  3. mbauman

    CSの人にとって「順序」とはリストの並びのことだ。しかし他のほとんど全員は操作の*時間的*な順序を考える。そしてその場合、確かに右か左から「開始」する。

    遅延/遅延評価される操作をたくさん扱うと、ただ混乱するだけだ。

  4. kccqzy

    AIはfoldl'やfoldr(特にfoldr)を、Map上の類似版も含めて、同じことをもっと単純でわかりやすい方法で実現できる場合でも過剰に使う傾向があることに気づいた。

    AIが複雑な蓄積関数を伴うfoldrを書いたら、カスタムのモノイド構造を定義してfoldMapを使うようにAIに促すだろう。そうすれば読者は非対称な蓄積関数について考えずに、マッピング操作と結合的な結合関数を別々に考えれば済む。蓄積関数の2つの役割を分離するのは可読性を高める素晴らしいテクニックだ。人間が主にコードを読むなら、優れたトレードオフだ。

  5. lukebitts

    とても興味深い記事だった。数年前に惨敗したHaskellの学習をもう一度やってみたくなる。

この日のほかの記事

2026-10-05