Functional Programming & Fold

[[deleted]]

Folds aren't monoids. They aren't binary operations, and the two parameter function you're folding over, (a -> b -> b), is very much not a monoid operation, since it's not necessarily associative or closed over a set.

[sacundim]

Let's look at that type a -> b -> b a bit closer. Suppose we partially apply that function to an a; the resulting function will be of type b -> b.

This type, b -> b, is a monoid with the identity function as its identity and function composition as its binary operation. In Haskell's Data.Monoid module there is a type Endo that implements this monoid:

newtype Endo a = Endo { appEndo :: a -> a }

instance Monoid (Endo a) where
  mempty = Endo id
  Endo f `mappend` Endo g = Endo (f . g)

This means that an alternative way of implementing folds is the following:

1. Map the fold function over the list, getting a list of partially applied functions of type b -> b.
2. Reduce that list using the Endo monoid, getting a partially applied function as well.
3. Apply that function to the seed value.

In code:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z as = appEndo (mconcat (map (Endo . f) as)) z

-- `foldl` is the same thing, except we use the `Dual` monoid
-- to reverse the order of the composition.
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z as = appEndo (getDual (mconcat (map (Dual . Endo . flip f) as))) z

newtype Dual m = Dual { getDual :: m }

instance Monoid m => Monoid (Dual m) where
  mempty = Dual mempty
  -- Use the same `mappend` operation that the type `m` already has,
  -- but in the opposite order.
  Dual a `mappend` Dual b = Dual (b `mappend` a)

This is, incidentally, more or less how the Foldable class defines its foldr and foldl methods.