haskell-jp / questions #101 at 2022-06-10 10:11:54 +0900

foldr と foldl で結果が異なるような場合ってありますか？

意図がよくわかっていないので希望されてるものかわからないですが，

Prelude> foldl const 0 [1..9]
0
Prelude> foldr const 0 [1..9]
1

おお、それだ！

ありがとうございます。

若干混み入った例だと、N-進表記を直す際にうっかり foldl と foldr をまちがえて結果がかわってしまった経験がありますね。

ghci> foldl (\a b -> 10*a + b) 0 [1,2,3]
123

ghci> foldr (\a b -> 10*a + b) 0 [1,2,3]
60

素敵な例だ！

foldl (⊗) e と foldr (⊗) e が同じ関数になるには ⊗ が結合律を満したうえで、e が単位元であるか ⊗ が交換律を満す場合かな。(IFPH 2 ed)

そういえば浮動小数点数の加法は厳密には結合律を満たさないのでびっくりする例がつくれそう、ということで quickCheck に探してもらいました：

ghci> quickCheck $ \dbls -> foldr (+) 0.0 (dbls :: [Double]) === foldl (+) 0.0 dbls
*** Failed! Falsified (after 9 tests and 16 shrinks):     
[0.1,1.0,-6.2]
-5.1000000000000005 /= -5.1

ghci> foldr (+) 0.0 [0.1,1.0,-6.2]
-5.1000000000000005

ghci> foldl (+) 0.0 [0.1,1.0,-6.2]
-5.1

乗法の例：

ghci> quickCheck $ \dbls -> foldr (*) 1.0 (dbls :: [Double]) === foldl (*) 1.0 dbls
*** Failed! Falsified (after 7 tests and 11 shrinks):     
[-1.0e-2,0.1,-3.0]
3.0000000000000005e-3 /= 3.0e-3

なるほど。
さすがです。