Hacker News new | past | comments | ask | show | jobs | submit login

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



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 #)




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: