Functor and Foldable

Some type classes describe containers rather than values. Their instances are type constructors like Maybe, [], and Tree — types that take a type parameter.

Functor: mapping over anything

map works on lists. fmap works on any Functor — anything with values inside that can be transformed without changing the shape:

main :: IO ()
main = do
  print (fmap (+ 1) [1, 2, 3])
  print (fmap (+ 1) (Just 41))
  print (fmap (+ 1) Nothing)
  print (fmap length (Right "hello" :: Either String String))
  print (fmap length (Left "error" :: Either String String))
  print (fmap (* 2) ("label", 10))
  print ((* 2) <$> Just 5)

[2,3,4]
Just 42
Nothing
Right 5
Left "error"
("label",20)
Just 10

• <$> is fmap written as an operator — very common in real code.
• For Either, fmap changes only a Right; a Left (error) passes through untouched. For a pair, it changes only the second element.

-- illustrative: the class definition
class Functor f where
  fmap :: (a -> b) -> f a -> f b

Making your type a Functor

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

instance Functor Tree where
  fmap _ Leaf = Leaf
  fmap f (Node l x r) = Node (fmap f l) (f x) (fmap f r)

main :: IO ()
main = do
  let t = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)
  print (fmap (* 10) t)
  print (fmap show t)

Node (Node Leaf 10 Leaf) 20 (Node Leaf 30 Leaf)
Node (Node Leaf "1" Leaf) "2" (Node Leaf "3" Leaf)

A lawful Functor keeps the shape: fmap id changes nothing, and fmap (f . g) equals fmap f . fmap g. With the DeriveFunctor extension (on by default in GHC2021), deriving (Functor) writes this instance for you.

Foldable: reducing anything

Foldable is the class of structures you can fold into a summary value. sum, length, elem, maximum, null, foldr, and toList all work on any Foldable, not just lists:

import Data.Foldable (toList)

data Tree a = Leaf | Node (Tree a) a (Tree a)
  deriving (Show, Foldable)

main :: IO ()
main = do
  let t = Node (Node Leaf 1 Leaf) 2 (Node Leaf 3 Leaf)
  print (sum t, product t, length t, maximum t)
  print (elem 3 t, toList t)
  print (sum (Just 5), length (Just 'x'), length Nothing)
  print (length (1, 2))

(6,6,3,3)
(True,[1,2,3])
(5,1,0)
1

The last line surprises many people: a pair is Foldable over its second element only, so its length is 1. It's consistent with fmap on pairs, but a good reason to avoid folding over tuples.

Traversable, briefly

Traversable combines both ideas: traverse maps a function that can fail (or do I/O) over a structure, and collects the results — succeeding only if every element succeeds:

import Text.Read (readMaybe)

main :: IO ()
main = do
  print (traverse readMaybe ["1", "2", "3"] :: Maybe [Int])
  print (traverse readMaybe ["1", "two", "3"] :: Maybe [Int])
  print (sequence [Just 1, Just 2])
  mapM_ print (Just "mapM_ works on any Foldable")

Just [1,2,3]
Nothing
Just [1,2]
"mapM_ works on any Foldable"