Why Foldable foldMap Requires Monoid But foldr Doesn't¶

This blog discusses why the Foldable requires m as a monoid at least. Through the minimal requirements of them, we could better understand what happens during execution of foldable, and why we need it.

Foldable requires either function foldMap or function foldr. Inside the foldMap, the m must be a monoid at least. Conversely, foldr requires nothing but a new parameter b.

class Foldable (t :: Type -> Type) where
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b

Semigroup and Monoid¶

In math, monoid is a semigroup with an identity element, where \(e \cdot a = a \cdot e = a\). The semigroup is a set that satisfies the associative propriety, where \((a \cdot b) \cdot c = a \cdot (b \cdot c)\).

In haskell, semigroup allows you to organise the calculation because it's associative, as long as the order is reserved. The monoid identity element(marked as mempty in haskell) gives a way to provide the default value for monoid when you wouldn't/cannot find a proper element from another set. For example, i want to define a set of positive integers and add operation, and will ignore all negative input. The traditional way to implement is:

postiveAdd :: Int -> Int -> Int
postiveAdd a b 
    | a<0 = b
    | b<0 = a
    | otherwise = a + b

main :: IO ()
main = print (1 `postiveAdd` (-1) `postiveAdd` 3)

Using monoid, we can find the identity element for the value is lower than 0.

-- in the modular design, the type constructor shouldn't be exported
-- so users are forced to use our constructor
newtype PositiveNum = PositiveNum Int deriving (Show, Eq)

makePositiveNum :: Int -> PositiveNum
makePositiveNum x
  | x < 0     = mempty
  | otherwise = PositiveNum x

instance Semigroup PositiveNum where
  PositiveNum a <> PositiveNum b = PositiveNum $ a + b

instance Monoid PositiveNum where
  mempty = PositiveNum 0

foldMap: Why Monoid Is Required¶

The t is a function which receives a type and emit another type. The m is a single type, such as Maybe String or Maybe [Int]. The Maybe Int is a semigroup and not a monoid because it doesn't implements the <>.

When calling foldMap, the t disappears from the result.

class Foldable (t :: Type -> Type) where
  foldMap :: Monoid m => (a -> m) -> t a -> m

That's because we map the value from t a and pass it to the function a -> m. Everything goes well if you could extract the value from t a, like Just 1, [1,2,3].

However, what if the t a value is somehow empty in the t a representation such as Nothing, []? The somehow empty refers to the state of foldable typeclass itself, instead of the value with type a it holds.

During implementation, designer uses identity element for certain cases based on the foldable logic. For example, you can treat both Bingo and Nothing' doesn't make sense on a monoid so you map them as mempty.

data  Maybe' a  =  Nothing' | Bingo | Just' a

instance Functor Maybe' where
    fmap _ Nothing' = Nothing'
    fmap _ Bingo = Bingo
    fmap f (Just' a) = Just' $ f a 

maybe' :: b -> (a->b) -> Maybe' a -> b
maybe' n _ Nothing' = n
maybe' n _ Bingo = n
maybe' _ f (Just' a)  = f a 

instance Foldable Maybe' where
  foldMap :: (Monoid m) => (a -> m) -> Maybe' a -> m
  foldMap = maybe' mempty

main :: IO ()
main = do
    print $ foldMap (++"hello") (Just' "world")
    print $ foldMap (++"hello") Nothing'
    print $ foldMap (++"hello") Bingo

The conclusion is, because empty/abnormal values in t doesn't make sense during mapping, we need an identity element for such cases. As a result, Foldable requires at least a monoid.

foldr: Why It Doesn't Require Monoid¶

After learning the foldMap, we know that a fallback value is needed for the t. However, foldr provides a different way than monoid. Instead of using the mempty, it requires users to pass a default value so the foldable could know how to handle the abnormal case.

Example: How Maybe Implements the Foldable¶

See the source code here.

The function maybe clearly conveys the idea of designer uses identity element for certain cases based on the foldable logic. Because Nothing doesn't make sense to map any value inside a monoid, we choose mempty to represent it.

maybe :: b -> (a -> b) -> Maybe a -> b
maybe n _ Nothing  = n
maybe _ f (Just x) = f x

instance Foldable Maybe where
    foldMap = maybe mempty

    foldr _ z Nothing = z
    foldr f z (Just x) = f x z

    foldl _ z Nothing = z
    foldl f z (Just x) = f z x

Warning: Foldable Implementation Should Ignore Underlying Type¶

If a foldable typeclass receives at least one type, we shouldn't limit the type of a inside foldable instance like this because it's not the scope of foldable to care.

data MaybeF a  =  Nothing' | Just' a

instance Functor MaybeF where
    fmap _ Nothing' = Nothing'
    fmap f (Just' a) = Just' $ f a 

maybef :: (Monoid a, Ord a) => b -> (a->b) -> MaybeF a -> b
maybef n _ Nothing' = n
maybef n f (Just' a) 
        | a < mempty = n
        | otherwise = f a

-- DON'T DO THIS!
instance Foldable MaybeF where
  foldMap :: (Monoid a, Ord a, Monoid m) => (a -> m) -> MaybeF a -> m
  foldMap = maybef mempty

If you do want this feature, creating a wrapper for it because it's out of the scope of Foldable.