Hacker News new | ask | show | jobs
by SamReidHughes 4067 days 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.
2 comments
bsummer4 4067 days 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
link
bsummer4 4067 days 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 #)
link
tel 4067 days 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
    ((* + *) + *) + (* + (* + *))
link
SamReidHughes 4067 days ago
Oh God, right. The changes over the years have left me bamboozled. Is (.) fmap yet?
link