Haskell Foldables

Is a Type Class for generalising folding up values in data structures of any parameterised Type.

Haskell Declaration

Built-in class declaration from Data.Foldable:

class foldable t where
  fold :: Monoid a => t a -> a
  foldMap :: Monoid b => (a -> b) -> t a -> b
  foldr :: (a -> b -> b) -> b -> t a -> b
  foldl :: (a -> b -> a) -> a -> t b -> a

where by convention foldable types are denoted by t.

One must define either foldMap or foldr as all other functions can be derived form either of these.

Other Primitives

In addition to the four folding primitives above the Foldable class also comes with the following useful functions for combining values in a data structure:

null :: t a -> Bool
length :: t a -> Int
elem :: Eq a => a -> t a -> Bool
maximum :: Ord a => t a -> a
minimum :: Ord a => t a -> a
sum :: Num a => t a -> a
product :: Num a => t a -> a

It also includes versions of foldr and foldl for structures containing at least one element (i.e. non-empty), which therefore do not need a starting value:

foldr1 :: (a -> a -> a) -> t a -> a
foldl1 :: (a -> a -> a) -> t a -> a

Finally it contains a primitive for flattening a data structure into a List.

toList :: t a -> [a]

This can be used to provide default definitions for the other primitives in the class in terms of the corresponding primitives for lists.

Default Relations

The following are default definitions that define relationships between primitives described above

fold = foldMap id
foldMap f = foldr (mappend . f) mempty
toList = foldMap (\x -> [x])

Examples

Lists as Foldable

instance Foldable [] where
  -- fold :: Monoid a => [a] -> a
  fold [] = mempty
  fold (x:xs) = x `mappend` fold xs
 
  -- foldMap :: Monoid b => (a -> b) -> [a] -> b
  foldMap _ []  = mempty
  foldMap f (x:xs) = f x `mappend` foldMap f xs
 
  -- foldr :: (a -> b -> b) -> b -> [a] -> b
  foldr _ v [] = v
  foldr f v (x:xs) = f x (foldr f v xs)
 
  -- foldl :: (a -> b -> a) -> a -> [b] -> a
  foldl _ v [] = v
  foldl f v (x:xs) = foldl f (f v x) xs

Binary Tree as Foldable

instance Foldable Tree where
  -- fold :: Monoid a => Tree a -> a
  fold (Leaf x)   = x
  fold (Node l r) = fold l ‘mappend‘ fold r
 
  -- foldMap :: Monoid b => (a -> b) -> Tree a -> b
  foldMap f (Leaf x)   = f x
  foldMap f (Node l r) = foldMap f l ‘mappend‘ foldMap f r
 
  -- foldr :: (a -> b -> b) -> b -> Tree a -> b
  foldr f v (Leaf x)   = f x v
  foldr f v (Node l r) = foldr f (foldr f v r) l
 
  -- foldl :: (a -> b -> a) -> a -> Tree b -> a
  foldl f v (Leaf x)   = f v x
  foldl f v (Node l r) = foldl f (foldl f v l) r