Foldable Type Class – Haskell

Haskell’s Foldable type class is a powerful abstraction for working with data structures that can be “folded” into a single result. Folding is the process of reducing a collection of elements into a summary value, such as a total, a concatenation, or a boolean.

This article explains the Foldable type class, its key functions, and how to use it effectively in your Haskell programs.

What is the Foldable Type Class?

The Foldable type class, defined in the Data.Foldable module, represents data structures that can be traversed and reduced to a single value. It generalizes folding operations beyond lists to include other data structures like Maybe, Tree, and custom containers.

Type Class Definition

Here’s a simplified version of the Foldable type class:

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

• t: The container type (e.g., [], Maybe, Tree).
• a: The type of elements in the container.
• b: The result type of the fold.

Core Functions of Foldable

The Foldable type class provides several functions for folding and summarizing data structures:

1. foldr (Right Fold)

foldr processes elements from right to left.

foldr :: (a -> b -> b) -> b -> t a -> b

Parameters:

• A binary function (a -> b -> b).
• An initial value of type b.
• A Foldable structure t a.

Example:

foldr (+) 0 [1, 2, 3]  -- Result: 6 (1 + (2 + (3 + 0)))

2. foldl (Left Fold)

foldl processes elements from left to right.

foldl :: (b -> a -> b) -> b -> t a -> b

Example:

foldl (+) 0 [1, 2, 3]  -- Result: 6 (((0 + 1) + 2) + 3)

3. foldMap

foldMap maps each element of the structure to a monoid and combines the results.

foldMap :: Monoid m => (a -> m) -> t a -> m

Example:

foldMap Sum [1, 2, 3]  -- Result: Sum {getSum = 6}
foldMap (:[]) [1, 2, 3] -- Result: [1, 2, 3]

Other Useful Functions in Foldable

1. fold: Combines all elements of a container using a monoid.

fold :: Monoid m => t m -> m

-- Example:
fold [Sum 1, Sum 2, Sum 3]  -- Result: Sum {getSum = 6}

2. toList: Converts a Foldable structure to a list.

toList :: Foldable t => t a -> [a]

-- Example:
toList (Just 5)  -- Result: [5]

3. null: Checks if a structure is empty.

null :: Foldable t => t a -> Bool

-- Example:
null []     -- Result: True
null (Just 3) -- Result: False

4. length: Counts the number of elements in a structure.

length :: Foldable t => t a -> Int

-- Example:
length [1, 2, 3]  -- Result: 3

5. sum, product: Sums or multiplies all elements in a structure.

sum :: (Foldable t, Num a) => t a -> a
product :: (Foldable t, Num a) => t a -> a

Foldable Beyond Lists

The power of Foldable lies in its ability to work with various data structures.

1. With Maybe

Folding a Maybe structure operates on its single element or handles Nothing gracefully.

Example:

foldr (+) 0 (Just 5)  -- Result: 5
foldr (+) 0 Nothing   -- Result: 0

2. With Tree

For custom data structures, such as a binary tree, you can implement the Foldable instance to enable folding.

Example:

data Tree a = Leaf | Node a (Tree a) (Tree a)

instance Foldable Tree where
  foldr f acc Leaf = acc
  foldr f acc (Node x left right) = foldr f (f x (foldr f acc right)) left

Using foldr on a tree:

tree = Node 1 (Node 2 Leaf Leaf) (Node 3 Leaf Leaf)
foldr (+) 0 tree  -- Result: 6

Benefits of Foldable

1. Generalized Operations:
   • Write code that works with any Foldable structure, not just lists.
2. Code Reusability:
   • Functions like sum, length, and toList work across different containers.
3. Abstraction:
   • Focus on what to compute, not how to traverse the structure.

Limitations of Foldable

1. No Traversal Guarantees:
   • Foldable doesn’t guarantee traversal order, which depends on the specific data structure.
2. Not Suitable for All Use Cases:
   • For operations requiring element access by index, Foldable is insufficient.

Conclusion

The Foldable type class in Haskell abstracts the idea of folding, enabling you to reduce and summarize various data structures efficiently. Whether you’re working with lists, Maybe, or custom data types like trees, Foldable provides a powerful toolkit for functional programming. By understanding Foldable, you can write more generic, reusable, and elegant code that focuses on computations rather than the specifics of data traversal.