Learn

Foldable and Traversable are the type classes that generalize folding and traversing over data structures. LYAH's later chapters and Real World Haskell's chapter on advanced typeclasses cover them.

Foldable — anything you can fold

The key method:

class Foldable t where
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldl :: (b -> a -> b) -> b -> t a -> b
    -- ... and many more

Lists, Maps, Sets, Trees, Maybe — all Foldable. You can sum, length, elem, minimum, maximum, foldr, foldl on any of them.

import Data.Foldable

sum [1, 2, 3]               -- 6
sum (Just 5)                 -- 5 (Maybe is Foldable!)
sum Nothing                  -- 0

length [1, 2, 3]             -- 3
length (Just 5)              -- 1
length Nothing               -- 0

elem 3 [1, 2, 3]             -- True
elem 3 (Just 3)              -- True

Surprising: Maybe is Foldable, with Nothing having length 0 and Just x having length 1.

Common Foldable functions

sum, product :: (Foldable t, Num a) => t a -> a
minimum, maximum :: (Foldable t, Ord a) => t a -> a
length :: Foldable t => t a -> Int
null :: Foldable t => t a -> Bool         -- empty?
elem :: (Foldable t, Eq a) => a -> t a -> Bool
any, all :: Foldable t => (a -> Bool) -> t a -> Bool
foldr, foldl :: ...
foldr', foldl' :: strict versions
toList :: Foldable t => t a -> [a]         -- collapse to list

Most code uses sum, length, elem, any, all, foldr. Same names work on lists, Maps, Sets — that's the polymorphism win.

Strict folds

import Data.Foldable (foldl')

foldl' (+) 0 [1..1_000_000]    -- strict, linear time
foldl  (+) 0 [1..1_000_000]    -- lazy, builds a thunk pile

Always prefer foldl' over foldl for numeric folds. Lazy foldl builds up unevaluated additions — stack overflow or memory blowup on large inputs. The space leak is so common it's a meme.

Traversable — fold + effect

Like Foldable but threads an EFFECT through the iteration:

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Reads: "given a function that maps each element to an effectful computation, produce one effect that yields the whole transformed structure."

Practical use

Read N lines, parsing each:

import Text.Read (readMaybe)

parseAll :: [String] -> Maybe [Int]
parseAll = traverse readMaybe

parseAll ["1", "2", "3"]    -- Just [1, 2, 3]
parseAll ["1", "abc", "3"]  -- Nothing — first failure aborts

traverse runs readMaybe on each, threading the Maybe monad. ANY failure → Nothing; ALL success → Just [results].

IO over a list:

import Data.Traversable

greetAll :: [String] -> IO ()
greetAll = traverse_ (\n -> putStrLn ("Hello, " ++ n))

-- Or for results:
data <- traverse readFile ["a.txt", "b.txt", "c.txt"]
-- IO [String]

traverse returns one big IO action that executes each in sequence.

sequence — the simpler version

sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

Flips the structure: [Maybe Int] -> Maybe [Int], [IO String] -> IO [String], etc.

sequence [Just 1, Just 2, Just 3]      -- Just [1, 2, 3]
sequence [Just 1, Nothing, Just 3]     -- Nothing
sequence [readFile "a", readFile "b"]  -- IO [String]

sequence = traverse id. traverse f = sequence . fmap f. Two views of the same operation.

When to use which

• Foldable (sum, length, etc.) — collapsing a structure to a single value
• Traversable (traverse, sequence) — when each element produces an EFFECT (Maybe, Either, IO) and you want one combined effect
• map / fmap — pure transformation, no effects

Common mistakes

• Using non-strict foldl on numbers — space leak. Always foldl' for numeric folds.
• Confusing traverse and mapM — mapM is traverse for monads (essentially). Modern Haskell uses traverse.
• Calling sum or length on Maybe unintentionally — works but might surprise readers.
• Sequencing IO actions when you want them in a specific order — traverse preserves order; if order matters, double-check the type's traversal semantics.
• Skipping Foldable/Traversable — basics are simple; learning them unlocks a huge chunk of standard library.