左と右は対称的ではなかった！？ Haskellのfoldrでアハ体験

概要

foldlとfoldrについて、

• foldrなら無限リストを扱える
• 逆ポーランド記法ならfoldlとfoldrは入れ替わる？

というような話題に関して少し掘り下げた記事です。

注意

この記事を読むと、左と右が本質的に対称的でない概念であるような錯覚を起こします。子どもに左右の概念を教育しているママ/パパの方はご注意ください。

また、もともとQiitadonのトゥートだったので多少文体が変ですが、ご容赦ください。

左右の難しさとfoldrの"操作"と無限リスト

元トゥート（の一部）

foldl/foldrと左右って難しくて、記法に対する単純な左右ということでもない。

foldlは、二変数関数fを第一引数に受け取って、fに第二引数と第三引数のリストの頭を適用した結果をさらにfに適用する。ので、仮にfoldlという関数を素朴に逆ポーランド記法で書くと、リストの表現の仕方にもよるけど、多分左右が"逆"になる。foldlというよりは、foldheadなんだよね。

ではfoldrはというと、foldtailで、単純なSumみたいなものは当然無限リストには適用できないんだけど、結果がリストになるような場合には、リストの先頭からi番目みたいなものの計算までは実は非正格であればうまく有限ステップで終わらせることができて、その意味で無限リストから無限リストを得るような場合にはうまく使える。

この話を、もう少し詳しくします。実際のHaskellのコード断片を眺めます。

すりぬけの術

foldr (+) 0 (1:2:3:[])
          == 1 +           foldr (+) 0 (2:3:[])
          == 1 + (2 +      foldr (+) 0 (3:[])
          == 1 + (2 + (3 + foldr (+) 0 []))
          == 1 + (2 + (3 + 0))

これ、foldr (+) 0という演算子がすり抜けていると思ってほしい。
foldr=Fとして、ちょっと違う書き方をすると、

             F (+) 0 (1 : 2 : 3 : [])
          == 1 + F (+) 0 (2 : 3 : [])
          == 1 + (2 + F (+) 0 (3 : [])
          == 1 + (2 + (3 + F (+) 0 []))
          == 1 + (2 + (3 + 0))

もっとわざとらしく、F (+) 0 = Gと書いて、1:2:3も括弧を補って書くと、

             G (1 : (2 : (3 : [])))
          == (1 + G (2 : (3 : [])))
          == (1 + (2 + G (3 : [])))
          == (1 + (2 + (3 + G [])))
          == (1 + (2 + (3 + 0)))

こういうことになって、foldrが右（末尾）方向にすり抜けているというような見方もできる。foldrがせき止めているのか、foldr自体が右に抜けているのか、まあ式の見方としてはどちらでも良いといえば良いんだけど…。

無限リストとfoldr

[1..] == 1:2:3:[4..]であることに注意する。

foldr (+) 0 (1:2:3:[4..])
          == 1 +           foldr (+) 0 (2:3:[4..])
          == 1 + (2 +      foldr (+) 0 (3:[4..])
          == 1 + (2 + (3 + foldr (+) 0 [4..]))

これは、足し算だと無限に続いてしまうので計算は終わらない。のだけど、

foldr (:) [] (1:2:3:[4..])
          == 1 :           foldr (:) [] (2:3:[4..])
          == 1 : (2 :      foldr (:) [] (3:[4..])
          == 1 : (2 : (3 : foldr (:) [] [4..]))

これは、..の部分を計算しなくても、先頭の要素とか二つ目の要素とかは確定するよね、ということ。
その意味でfoldrは無限リストを扱える、tailまで行かなくても！

実例を挙げてみる：

a = foldr (:) [] (1:2:3:[4..])
main = putStrLn $ show (take 10 a)
-- [1,2,3,4,5,6,7,8,9,10]

こんなことは、素朴なfoldlではできない。

これはとても興味深い話で、「関数」というものを素朴に捉えると、中学校の数学で習うような写像を想像してしまい、foldrはリストの末尾から再帰的に計算をしなければならないようなイメージを持つ（場合がある）。

しかし、それはfoldrの性質の一部であって、この例のように引数として与える関数によっては末尾まで計算を行わなくても必要な計算が終了する事がある。foldlの素朴な実装は、実際にリストの先頭から正格的な評価をするにも関わらず。

ただの左右じゃん、と思ったら全然そんなことはない！

そういう話でした。おしまい