Becoming Productive in Haskell

Re:Becoming Productive in Haskell by bsummer4 on Friday April 24, 2015 @05:29PM (#9436122)

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

[ Parent | on HN ]

Re:Becoming Productive in Haskell by bsummer4 on Friday April 24, 2015 @06:14PM (#9436294)

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

[ Parent | on HN ]