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
((* + *) + *) + (* + (* + *))