Functors and monads are somewhat not going to change their names, partly because Haskell derives from math and those are what they're called over there.
But foldl' is horrible, I agree.
But foldl' is horrible, I agree.
1: fold :: (Foldable t,Monoid m) => t m -> m
The Monoid operation mappend is guaranteed to be associative, so the order is irrelevant. Data structures can fold in whatever way is most efficient for their structure.
It's true that lists and arrays are implemented as right folds, however the fold implementation for sets is neither:
From Data.Set:
fold = go
where go Tip = mempty
go (Bin 1 k _ _) = k
go (Bin _ k l r) = go l `mappend` (k `mappend` go r)
-- Here, I reorganized the code of `fold` to have the same shape as
-- `foldl/foldr` so that you can see the difference in structure more
-- clearly.
fold2 = fold3 mappend mzero
fold3 f z = go z
where
go z' Tip = z'
go z' (Bin _ x l r) = f (go f z' l) (f x (go f z' r))
foldl f z = go z
where
go z' Tip = z'
go z' (Bin _ x l r) = go (f (go z' l) x) r
foldr f z = go z
where
go z' Tip = z'
go z' (Bin _ x l r) = go (f x (go z' r)) l fold [[_ 4 _] 3 _] → f 4 (f 3 #)
fold2 f # [[_ 4 _] 3 _] → f (f # (f 4 #)) (f 3 #)
foldl f # [[_ 4 _] 3 _] → f (f # 4) 3
foldr f # [[_ 4 _] 3 _] → f 3 (f 4 #)
fold [[_ 4 _] 3 _]
f (go [_ 4 _]) (f 3 (go []))
f 4 (f 3 (go []))
f 4 (f 3 #)
fold2 [[_ 4 _] 3 _]
fold3 f # [[_ 4 _] 3 _]
f (go [_ 4 _]) (f 3 (go _))
f (f (go _) (f 4 (go _))) (f 3 (go _))
f (f # (f 4 # )) (f 3 # )
f (f # (f 4 # )) (f 3 # )
f (f # (f 4 #)) (f 3 #)
foldl f # [[_ 4 _] 3 _]
go # [[_ 4 _] 3 _]
go (f (go # [_ 4 _]) 3) _
f (go # [_ 4 _]) 3
f (go (f (go # _) 4) _) 3
f (go (f # 4) _) 3
f (f # 4) 3
foldr f # [[_ 4 _] 3 _]
go # [[_ 4 _] 3 _]
go (f 3 (go # [_ 4 _])) _
f 3 (go # [_ 4 _])
f 3 (go (f 4 (go # _)) _)
f 3 (f 4 (go # _))
f 3 (f 4 #) * + (* + (* + (* + (* + (* + *))))) versus
(((((* + *) + *) + *) + *) + *) + * versus
((* + *) + *) + (* + (* + *))