7 ms·

foldl' is a consistent and meaningful name. fold performs a fold without specifying an order[1], foldl folds from the left, and foldl' is a non-lazy version of

foldl' is a consistent and meaningful name. fold performs a fold without specifying an order[1], foldl folds from the left, and foldl' is a non-lazy version of of foldl. 1: fold :: (Foldable t,Monoid m) => t m -> m

SamReidHughes 11y ago
Is there a spec that leaves the order unspecified? Having it not be a right fold would be quite nutty. It is a right fold in implementation.
- bsummer4 11y ago
  Ugg, I had to spend a fair amount of time coming up with a good example. Hope this is helpful! 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
  - bsummer4 11y ago
    I went through some examples to make 100% sure that fold has different behavior than foldl/foldr: 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 #) Reductions: 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 #)
- tel 11y ago
  It's useful for more general folds over more general types. If you have a tree structure then you might not want to fold from the left or the right but instead in multiple places in parallel and then combine them at the end * + (* + (* + (* + (* + (* + *))))) versus (((((* + *) + *) + *) + *) + *) + * versus ((* + *) + *) + (* + (* + *))
  - SamReidHughes 11y ago
    Oh God, right. The changes over the years have left me bamboozled. Is (.) fmap yet?

SamReidHughes 11y ago

Is there a spec that leaves the order unspecified? Having it not be a right fold would be quite nutty. It is a right fold in implementation.

bsummer4 11y ago
Ugg, I had to spend a fair amount of time coming up with a good example. Hope this is helpful! 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
- bsummer4 11y ago
  I went through some examples to make 100% sure that fold has different behavior than foldl/foldr: 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 #) Reductions: 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 #)
tel 11y ago
It's useful for more general folds over more general types. If you have a tree structure then you might not want to fold from the left or the right but instead in multiple places in parallel and then combine them at the end * + (* + (* + (* + (* + (* + *))))) versus (((((* + *) + *) + *) + *) + *) + * versus ((* + *) + *) + (* + (* + *))
- SamReidHughes 11y ago
  Oh God, right. The changes over the years have left me bamboozled. Is (.) fmap yet?