Foldable

One class for every container

The fold of the earlier lesson works on lists. Foldable is the class of types that can be folded: it gives foldr and foldMap, and from those the library derives sum, product, length, elem, maximum, toList and a dozen more. A function written with the class works on every instance at once.

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

A list, a Maybe and a tree are all foldable: a list has its elements in order, a Maybe has zero or one, and a tree has them in the order its instance chooses. That is why sum (Just 5) is 5 and sum (Nothing :: Maybe Int) is 0.

foldMap and its helpers

foldMap maps each element to a Monoid and combines the results with <> and mempty. For String the monoid is concatenation, so foldMap show turns a list of numbers into one string:

module Main (main) where import Data.Foldable (toList) main :: IO () main = do print (foldMap show ([1, 2, 3] :: [Int]) :: String) print (foldMap show (Just (4 :: Int)) :: String) print (sum (Just (5 :: Int)) :: Int) print (toList (Just (7 :: Int)) :: [Int]) print (toList ([1, 2] :: [Int]) :: [Int])

ghc -Wall -O1 -o foldable foldable.hs
./foldable

"123"
"4"
5
[7]
[1,2]

The first line is the interesting one: three values become one string with no list in between, which is the same result as concatMap show and cheaper. The fourth and fifth show toList turning any foldable into a list, which is the bridge to the list functions that do not have a general version.

A Foldable tree

The tree of the recursion lesson gets a Foldable instance by one recursive definition: the fold of a node is the fold of the left subtree, then the value, then the right subtree, in the order the instance chooses. In-order is the natural choice for a search tree.

module Main (main) where import Data.Foldable (toList) data Tree a = Leaf | Node (Tree a) a (Tree a) deriving (Show) instance Foldable Tree where foldr _ z Leaf = z foldr f z (Node left value right) = foldr f (f value (foldr f z right)) left sample :: Tree Int sample = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf) main :: IO () main = do print (sum sample) print (toList sample) print (length sample)

ghc -Wall -O1 -o treefoldable treefoldable.hs
./treefoldable

6
[1,2,3]
3

Three library functions work on the tree without knowing what a tree is: sum adds the values, toList produces them in order and length counts them. The instance is four lines, and it replaces the three hand-written traversals of the recursion lesson at once. This is the payoff of the classes: one instance, and every function written against the class applies.

toList and the general functions

The functions that come with Foldable are worth knowing by name, because they replace a lot of glue:

A signature such as Foldable t => t a -> Int says the function needs to walk the container and nothing else, so it accepts a list, a tree, a Maybe and the containers of the next lessons. That is how a library writes one function where a beginner writes five, and why the class is worth understanding even when the code is short.

Foldable is the last lesson of Part 4. The next part goes to Traversable, which combines a fold with an effect, and then to Semigroup and Monoid, which give foldMap its combining operation.

Exercises

  1. Write countEven :: Foldable t => t Int -> Int with foldr and run it on a list and on a Maybe.
  2. Use foldMap show on a tree and compare it with show (toList tree).
  3. Add a Foldable instance for a type of your own with two constructors.
  4. Compute maximum (Just 3) and maximum (Nothing :: Maybe Int) and explain both results.
  5. Write toList for the tree by hand with foldr (:) [].
  6. Explain why Foldable is not enough to rebuild the container and which class does that.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does the Foldable class provide?

    Answer

    foldr and foldMap, and from them many container functions

    Foldable is the class of types that can be folded; the library derives sum, length, toList and others from its methods.

  2. What does sum (Just 5) return?

    Answer

    5

    Maybe is Foldable with zero or one element, so sum of Just 5 is 5.

  3. What does foldMap show [1, 2, 3] return?

    Answer

    "123"

    foldMap combines the shown values with the string monoid, which is concatenation.

  4. What does toList (Just 7) return?

    Answer

    [7]

    A Just has one element, so its list form is a singleton.

  5. What does this program print? module Main (main) where import Data.Foldable (toList) main :: IO () main = print (toList (Just (3 :: Int)) :: [Int])

    Answer

    [3]

    toList turns the single element of Just into a one-element list.

  6. What does a Foldable instance for a tree decide?

    Answer

    The order in which the fold visits the elements

    The instance defines foldr, and with it the order of toList.

  7. What does foldr on a tree in the lesson do for a node?

    Answer

    Folds the left subtree, then the value, then the right subtree

    The instance is in-order: left, value, right, which is why toList is sorted.

  8. Which functions work on any Foldable without a new definition?

    Answer

    sum, length and elem

    The Foldable methods are enough for these, while map needs a Functor and reverse needs a list.

  9. What does length (Just 3) return?

    Answer

    1

    length counts the elements of any Foldable, and Just has one.

  10. Why is Foldable not enough to rebuild a tree from a list?

    Answer

    It only folds; rebuilding needs a way to construct, which Traversable and the constructor provide

    Foldable consumes the structure, and the reconstruction needs the shape, which a fold alone does not keep.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev