Functors and applicatives

The Functor, Applicative, Foldable, and Traversable type classes are the foundation of Haskell’s higher-order programming. Together with Monad (treated separately in Monads), they constitute the type-class hierarchy that abstracts effects, sequencing, and composition. The mechanism is one of Haskell’s distinguishing contributions: a small set of laws-and-operations interfaces that subsume substantial programming patterns and admit substantial code reuse.

This page covers Functor, Applicative, Foldable, and Traversable — the four classes that every working Haskell programmer encounters routinely. The principal operations are fmap, <$>, <*>, pure, foldr, foldMap, traverse, and sequence.

Functor and fmap

A functor is a type constructor that admits a structure-preserving map:

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

The intuition: fmap lifts a function a -> b to a function f a -> f b, where f is the functor’s type constructor (a type variable of kind * -> *).

The standard instances:

instance Functor [] where
    fmap = map

instance Functor Maybe where
    fmap _ Nothing  = Nothing
    fmap f (Just x) = Just (f x)

instance Functor (Either e) where
    fmap _ (Left x)  = Left x
    fmap f (Right x) = Right (f x)

instance Functor IO where
    fmap = ioMap                  -- the IO monad's fmap

fmap admits one operation that works across all of them:

fmap (+ 1) [1, 2, 3]              -- [2, 3, 4]
fmap (+ 1) (Just 5)                -- Just 6
fmap (+ 1) Nothing                 -- Nothing
fmap (+ 1) (Right 10)              -- Right 11
fmap show getLine                  -- IO String -> IO String

The operator <$> is the infix synonym:

(<$>) = fmap

(+ 1) <$> [1, 2, 3]                -- [2, 3, 4]
show <$> getLine                    -- read a line, then show it

The <$> is the conventional infix form; it reads as “map over the structure”.

The Functor laws

Every Functor instance must satisfy:

-- Identity:
fmap id = id

-- Composition:
fmap (f . g) = fmap f . fmap g

The laws ensure the instance behaves like a structure-preserving map and not like an arbitrary function. The compiler does not check the laws; the implementer is responsible.

The laws together imply that a Functor instance is unique (up to behaviour) — there is at most one well-formed Functor instance for a given type constructor.

Applicative and <*>

A type constructor that admits both embedding (lifting a value) and applying a function inside the structure:

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

The intuition:

• pure takes a value and wraps it in the structure.
• <*> admits applying a function-inside-the-structure to a value-inside-the-structure.

The standard instances:

instance Applicative [] where
    pure x  = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

instance Applicative Maybe where
    pure = Just
    Just f  <*> Just x  = Just (f x)
    _       <*> _       = Nothing

instance Applicative IO where
    pure = return
    fAction <*> xAction = do
        f <- fAction
        x <- xAction
        return (f x)

The principal use is applying a multi-argument function to multiple effectful arguments:

add :: Int -> Int -> Int
add x y = x + y

addInMaybe :: Maybe Int -> Maybe Int -> Maybe Int
addInMaybe x y = add <$> x <*> y

addInMaybe (Just 1) (Just 2)        -- Just 3
addInMaybe Nothing (Just 2)         -- Nothing
addInMaybe (Just 1) Nothing         -- Nothing

The pattern reads: “fmap add over x (producing a Maybe (Int -> Int)), then apply the result to y”. The <$> and <*> chain admits multi-argument application without explicit case-by-case handling.

For three arguments:

add3 a b c = a + b + c
add3 <$> Just 1 <*> Just 2 <*> Just 3      -- Just 6
add3 <$> Just 1 <*> Nothing <*> Just 3     -- Nothing

The pattern generalises to any number of arguments.

The Applicative laws

Every Applicative instance must satisfy:

-- Identity:
pure id <*> v = v

-- Composition:
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

-- Homomorphism:
pure f <*> pure x = pure (f x)

-- Interchange:
u <*> pure y = pure ($ y) <*> u

The laws ensure the instance behaves like a context where computation may be applied; Applicative is the conventional interface for “context-aware function application”.

Convenience operators

Applicative admits a few useful operators:

(*>) :: Applicative f => f a -> f b -> f b      -- discard left, keep right
(<*) :: Applicative f => f a -> f b -> f a       -- discard right, keep left
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c

-- *> and <*:
putStrLn "starting" *> pure 42                   -- prints "starting", returns 42
getLine <* putStrLn "got it"                      -- reads a line, prints "got it"

-- liftA2 example:
liftA2 (+) (Just 1) (Just 2)                       -- Just 3

The *> and <* admit sequencing actions while keeping only one’s result.

Alternative

A subclass of Applicative for types that admit a notion of choice:

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a

The intuition: empty is the failure case; <|> admits “try this, or fall back to that”. The standard instances:

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

instance Alternative [] where
    empty = []
    (<|>) = (++)

Common uses:

findUser :: Int -> Maybe User
findUser id = lookupCache id <|> lookupDatabase id <|> Just defaultUser

-- For lists, <|> is concat:
[1, 2] <|> [3, 4]                 -- [1, 2, 3, 4]

The treatment is brief here; Alternative is principally useful in parsing libraries (Parsec, Megaparsec, Attoparsec) where <|> admits “try this parser, or that one”.

Foldable and reductions

A type constructor that admits reduction — collapsing a structure into a single value:

class Foldable t where
    foldr :: (a -> b -> b) -> b -> t a -> b
    foldMap :: Monoid m => (a -> m) -> t a -> m
    -- plus default-derived: foldl, sum, length, null, elem, ...

The principal operations:

length :: Foldable t => t a -> Int
sum :: (Foldable t, Num a) => t a -> a
product :: (Foldable t, Num a) => t a -> a
elem :: (Foldable t, Eq a) => a -> t a -> Bool
maximum, minimum :: (Foldable t, Ord a) => t a -> a
toList :: Foldable t => t a -> [a]
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

The standard instances:

instance Foldable [] where
    foldr = Prelude.foldr
    -- ...

instance Foldable Maybe where
    foldr _ z Nothing  = z
    foldr f z (Just x) = f x z
    -- ...

instance Foldable (Either e) where
    foldr _ z (Left _)  = z
    foldr f z (Right x) = f x z

instance Foldable Tree where
    foldr f z Leaf         = z
    foldr f z (Node l x r) = foldr f (f x (foldr f z r)) l

The mechanism admits writing one polymorphic version of each reduction:

sum [1, 2, 3, 4]                  -- 10 (list)
sum (Just 5)                       -- 5  (Maybe)
sum (Right 7)                      -- 7  (Either e)
sum tree                           -- works on any Foldable Tree

length [1, 2, 3]                   -- 3
length (Just 5)                    -- 1
length Nothing                      -- 0
length (Right 5)                   -- 1
length (Left "error")              -- 0

The conventional uses are aggregate operations — sum, average, count — that work uniformly across container types.

foldMap

A particularly elegant fold uses a Monoid:

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

The intuition: map every element to an m (a Monoid), then combine all the ms. The combination admits:

import Data.Monoid

-- Sum of a list of numbers:
total = getSum (foldMap Sum [1, 2, 3, 4])           -- 10

-- Concatenate a list of strings:
combined = foldMap show [1, 2, 3]                    -- "123"

-- Or-of-predicates:
anyMatch = getAny (foldMap (Any . (> 5)) [1, 6, 3])    -- True

The Sum, Product, Any, All, First, Last newtypes admit different Monoid instances on the same underlying type — the conventional Haskell idiom for “combine these values in a particular way”.

The full treatment of Monoid and Semigroup is in Polymorphism and elsewhere.

Traversable and effectful traversal

Traversable extends Foldable with the ability to traverse with effects:

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

The intuition: traverse f xs applies f to every element, collecting the effects, and produces a result with the original structure preserved. The mechanism admits effectful operations on a structure without changing its shape.

Common uses:

-- Read several integers:
readSeveral :: [String] -> Maybe [Int]
readSeveral = traverse readMaybe

readSeveral ["1", "2", "3"]              -- Just [1, 2, 3]
readSeveral ["1", "two", "3"]            -- Nothing

-- Run several IO actions:
results :: IO [String]
results = traverse readFile ["a.txt", "b.txt", "c.txt"]

-- Validate a list:
validate :: (a -> Either String b) -> [a] -> Either String [b]
validate = traverse

The construction traverse f reads as “apply f to each element, collect the effects, preserve the structure”. The mechanism subsumes much of what mapM, sequence, forM provide for lists.

mapM and sequence

For monadic effects, mapM and sequence are the same as traverse and sequenceA:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)
forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b)
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()

The _-suffixed variants discard the result; mapM collects results, mapM_ does not.

main = do
    contents <- mapM readFile ["a.txt", "b.txt"]   -- collect all contents
    forM_ contents putStrLn                          -- print each, discard result

    forM_ [1..10] $ \n -> do
        putStrLn $ "Processing " ++ show n
        process n

The patterns are pervasive in idiomatic Haskell IO code.

Common patterns

Multi-argument application with <$> and <*>

greet :: String -> Int -> String
greet name age = "Hello, " ++ name ++ ", age " ++ show age

-- Lift to Maybe:
greetMaybe :: Maybe String -> Maybe Int -> Maybe String
greetMaybe = liftA2 greet

-- Or with <$> and <*>:
greetMaybe = (greet <$>) <*> id   -- (less idiomatic)

-- The conventional form:
result :: Maybe String
result = greet <$> Just "Alice" <*> Just 30   -- Just "Hello, Alice, age 30"

The pattern is the conventional Haskell idiom for “apply a multi-argument pure function to multiple effectful arguments”.

traverse for a list of fallible operations

parseEach :: [String] -> Either String [Int]
parseEach = traverse parseInt
  where
    parseInt s = case reads s of
        [(n, "")] -> Right n
        _         -> Left ("could not parse: " ++ s)

parseEach ["1", "2", "3"]               -- Right [1, 2, 3]
parseEach ["1", "two", "3"]             -- Left "could not parse: two"

The mechanism admits “fail at the first failure, return the failure” — the conventional Haskell idiom for short-circuiting validation.

foldMap for monoid-driven aggregation

import Data.Monoid

countWords :: [String] -> Int
countWords = getSum . foldMap (Sum . length . words)

data Stats = Stats { count :: !Int, total :: !Int }
    deriving Show

instance Semigroup Stats where
    Stats c1 t1 <> Stats c2 t2 = Stats (c1 + c2) (t1 + t2)

instance Monoid Stats where
    mempty = Stats 0 0

makeStats :: Int -> Stats
makeStats n = Stats 1 n

aggregateStats :: [Int] -> Stats
aggregateStats = foldMap makeStats

The pattern admits combining heterogeneous values through a Monoid instance. Many libraries (like Statistics) use this construction.

sequence to collect IO results

results :: IO [Result]
results = sequence [doAction1, doAction2, doAction3]

-- Equivalent:
results = do
    r1 <- doAction1
    r2 <- doAction2
    r3 <- doAction3
    return [r1, r2, r3]

The sequence form is more compact when the actions are independent.

for_ for effectful iteration without result

import Data.Foldable (for_)

main = for_ [1..10] $ \n -> do
    putStrLn $ "Item " ++ show n
    process n

for_ is the flipped form of traverse_; the choice is stylistic.

A note on monads

The Monad type class extends Applicative with sequential composition:

class Applicative m => Monad m where
    return :: a -> m a            -- = pure
    (>>=)  :: m a -> (a -> m b) -> m b

Monad is necessary when the structure of the second computation depends on the result of the first; Applicative is enough when the computations are independent. The full treatment is in Monads.

The conventional advice:

• Functor for “map a function inside a structure”.
• Applicative for “combine independent effectful values with a multi-argument function”.
• Monad for “the next computation depends on the previous one”.
• Foldable and Traversable for “iterate over a structure”.

The combination — small set of operations, laws that ensure consistent behaviour, code reuse across many types — is one of Haskell’s most distinctive contributions.