Haskell 8: Functors and the Laws of Mapping

Part 8 of Haskell from First Principles.

Load complete definitions from a .hs file and try expressions in GHCi. Signatures of existing Prelude methods explain their types; they are not new declarations to paste into a module. Treat alternative data declarations and instance implementations as separate examples.

map transforms elements of a list. Type classes let different types implement a shared interface. Putting these ideas together gives us Functor: an interface for mapping functions through a structure or computational context.

The familiar examples are lists, optional values, and trees. Functions themselves also have a Functor instance, so the idea reaches beyond containers. We will derive the interface, implement instances, and explain the laws that make mapping predictable.

For a closer look at constructors with several type parameters, read the companion article Functors with Multiple Type Parameters, which also introduces Bifunctor.

8.1 Start with map

Recall the list function:

map :: (a -> b) -> [a] -> [b]
 
-- map (+1) [1,2,3]            -- [2,3,4]
-- map show ([1,2,3] :: [Int]) -- ["1","2","3"]

The first example changes the values while retaining the list’s length and order. The second can also change the element type: an [Int] becomes a [String], while the outer type constructor remains [].

Mathematically, its type has the form:

$$\mathrm{map}:(A\to B)\to [A]\to [B].$$

Can we perform the corresponding transformation for something other than a list?

8.2 A mapping operation for Maybe

The standard Maybe type represents absence or presence:

-- Already provided by the Prelude:
-- data Maybe a = Nothing | Just a

To increment an optional integer, we could write:

incrementMaybe :: Maybe Int -> Maybe Int
incrementMaybe Nothing = Nothing
incrementMaybe (Just x) = Just (x + 1)
 
-- incrementMaybe (Just 3) -- Just 4
-- incrementMaybe Nothing  -- Nothing

But this mixes two concerns: handling absence and choosing an integer transformation. Factor out the transformation:

mapOptional :: (a -> b) -> Maybe a -> Maybe b
mapOptional _ Nothing = Nothing
mapOptional g (Just x) = Just (g x)
 
-- mapOptional (+1) (Just 3)               -- Just 4
-- mapOptional show (Just (3 :: Int))       -- Just "3"
-- mapOptional (+1) (Nothing :: Maybe Int) -- Nothing

This is the source tutorial’s mapMaybe idea, renamed here to avoid confusion with the different standard function Data.Maybe.mapMaybe.

Compare the signatures:

map         :: (a -> b) -> [a]     -> [b]
mapOptional :: (a -> b) -> Maybe a -> Maybe b

Both apply a transformation while preserving the surrounding kind of context. Only the type constructor differs.

8.3 The Functor type class

The essential interface is:

-- Simplified presentation of the existing Prelude class.
class Functor f where
  fmap :: (a -> b) -> f a -> f b

The full standard class also has <$ with a default implementation; defining fmap is sufficient for the examples here. Its qualified type is:

fmap :: Functor f => (a -> b) -> f a -> f b

We replace the list constructor [] in map with a variable f:

Choice of f	Specialized mapping type
[]	(a -> b) -> [a] -> [b]
Maybe	(a -> b) -> Maybe a -> Maybe b
Tree	(a -> b) -> Tree a -> Tree b
Either String	(a -> b) -> Either String a -> Either String b

The abstraction is over the type constructor, as well as over the input and output element types. Given g :: a -> b, fmap g is a function f a -> f b.

8.4 Type constructors and kinds

Int is a complete type of values. Maybe still needs a type argument: applying it to Int produces the type Maybe Int. This is application at the type level, analogous in syntax to applying a function to a value.

Haskell uses kinds to classify types and type constructors. For the ordinary types in this post:

Type expression	Kind	Interpretation
Int	Type	A complete type
Bool	Type	A complete type
Maybe	Type -> Type	Takes one type argument
Maybe Int	Type	The result of applying Maybe
Either	Type -> Type -> Type	Takes two type arguments
Either String	Type -> Type	Still needs its second argument
Tree	Type -> Type	A parameterized tree type

Type names the kind of ordinary lifted types used here. Older notation writes this kind as *, so you may see * -> * where this post writes Type -> Type. These are kind descriptions, rather than value-level type signatures for identifiers such as Int.

In f a, f is applied to a type argument and must produce another ordinary type. Therefore Functor requires:

$$f:\mathrm{Type}\to \mathrm{Type}.$$

Functor Maybe makes sense; Functor Int does not, because Int cannot take another type argument. Either has too many remaining arguments, but Either String has exactly the right kind.

This is partial application at the type level. Fixing Either’s first parameter leaves a unary type constructor, just as fixing one argument of a curried function leaves a function awaiting its next argument.

8.5 Implement a custom Functor

To avoid redefining the standard Maybe instance, introduce a similar custom type:

data Optional a
  = Missing
  | Present a
  deriving (Eq, Show)
 
instance Functor Optional where
  fmap _ Missing = Missing
  fmap g (Present x) = Present (g x)

Inside this instance, mapping has the specialized type:

-- Specialized method type:
-- fmap :: (a -> b) -> Optional a -> Optional b

For Missing, there is no value to transform. For Present x, apply the supplied function and keep the Present constructor.

fmap (+1) (Present 3)                -- Present 4
fmap show (Present (3 :: Int))        -- Present "3"
fmap (+1) (Missing :: Optional Int)  -- Missing

The mapping operation does not decide whether an input is missing. It transforms the value when one is available. The class-and-instance mechanism is the same as for Eq; the new feature is that the instance parameter is a type constructor.

8.6 Lists, Maybe, and Either

The standard instances let one method express several useful behaviors:

-- Transform every list element.
fmap (+1) [1,2,3]
-- [2,3,4]
 
-- Transform an optional value when it exists.
fmap (+1) (Just 3)
-- Just 4
 
fmap (+1) (Nothing :: Maybe Int)
-- Nothing
 
-- Transform a Right value while preserving a Left value.
fmap (+1) (Right 3 :: Either String Int)
-- Right 4
 
fmap (+1) (Left "error" :: Either String Int)
-- Left "error"

Why does Either transform only Right? Its parameters play different roles:

-- Standard data type, shown for explanation:
-- data Either e a = Left e | Right a
 
-- Illustration of the existing instance; do not redefine it.
instance Functor (Either e) where
  fmap _ (Left err) = Left err
  fmap g (Right x) = Right (g x)

We fix e and map over the last parameter, a:

-- Specialized method type:
-- fmap :: (a -> b) -> Either e a -> Either e b

Left often represents an error and Right a successful result. The instance’s behavior follows the type parameters, regardless of what we choose those constructors to mean in a particular program.

parseResult :: Either String Int
parseResult = Right 42
 
-- fmap show parseResult
-- Right "42" :: Either String String

The error type remains String; the success type changes from Int to String. We can reuse the error-handling behavior without writing the same case analysis at every call site.

8.7 Mapping over a recursive tree

Recursive data types can support the same interface:

data Tree a
  = Empty
  | Node a (Tree a) (Tree a)
  deriving (Eq, Show)
 
mapTree :: (a -> b) -> Tree a -> Tree b
mapTree _ Empty = Empty
mapTree g (Node x left right) =
  Node (g x) (mapTree g left) (mapTree g right)

mapTree already has the shape required by Functor. Put the traversal in the instance:

instance Functor Tree where
  fmap _ Empty = Empty
  fmap g (Node x left right) =
    Node (g x) (fmap g left) (fmap g right)
 
tree :: Tree Int
tree =
  Node 5
    (Node 2 Empty Empty)
    (Node 8 Empty Empty)

Mapping increments the labels while keeping all branches in their original positions:

Before fmap (+1)        After fmap (+1)
 
        5                       6
       / \                     / \
      2   8                   3   9

In constructor notation:

fmap (+1) tree
-- Node 6 (Node 3 Empty Empty) (Node 9 Empty Empty)
 
fmap show tree
-- Node "5" (Node "2" Empty Empty) (Node "8" Empty Empty)

The second expression produces Tree String. Each caller chooses a transformation, while the instance centralizes the recursive traversal.

8.8 The two Functor laws

A method with the right type is not enough to make an instance a lawful functor. Mapping must also preserve identity and composition. These laws are part of the standard Functor contract.

Identity

The identity function leaves its argument unchanged:

id :: a -> a
id x = x

The first law is:

fmap id = id

This is an equation expressing equivalence of functions, rather than an expression using Haskell’s (==) operator. In particular, Haskell does not supply a general equality operation on functions.

Examples are:

fmap id ([1,2,3] :: [Int]) -- [1,2,3]
fmap id (Just (5 :: Int))   -- Just 5
fmap id tree               -- the original tree

For Maybe, inspect both constructors:

fmap id Nothing
  = Nothing
 
fmap id (Just x)
  = Just (id x)
  = Just x

For the tree, the corresponding proof follows the recursive structure: Empty remains Empty, and a node remains the same when identity leaves its label and, recursively, both subtrees unchanged.

Composition

Function composition means:

(g . h) x = g (h x)

The second law is:

fmap (g . h) = fmap g . fmap h

Equivalently, for an input value:

fmap (g . h) value = fmap g (fmap h value)

We can compose first and map once, or map each transformation in sequence. The results must agree:

fmap (show . (+1)) (Just (3 :: Int))
-- Just "4"
 
fmap show (fmap (+1) (Just (3 :: Int)))
-- Just "4"

For a present value, both routes reduce to the same expression:

fmap (g . h) (Just x)
  = Just ((g . h) x)
  = Just (g (h x))
 
fmap g (fmap h (Just x))
  = fmap g (Just (h x))
  = Just (g (h x))

For Nothing, both return Nothing.

These are the usual equational arguments for the defined values and pure functions under discussion. Haskell also has nontermination, partially defined values, and strictness-sensitive observations; those require care in broader semantic claims. We will use both laws as the explicit contract rather than assert an unconditional theorem about all well-typed Haskell implementations.

A well-typed instance that breaks the laws

Consider this deliberately bad implementation:

data Reversing a = Reversing [a]
  deriving (Eq, Show)
 
-- Deliberately unlawful: do not use this as a Functor design.
instance Functor Reversing where
  fmap g (Reversing xs) =
    Reversing (reverse (map g xs))

It has the required method type, but:

fmap id (Reversing [1,2,3])
-- Reversing [3,2,1]

Identity fails because mapping performs an unrelated reversal. Composition also fails on this example: mapping once reverses once, while mapping twice reverses twice.

For lists and trees, “preserve shape” is a useful guide: mapping should not reorder, add, or remove the original positions. More generally, the laws govern how the context behaves; the next example shows why every functor need not have a literal container shape.

8.9 Functions are functors, too

Fix a function’s input type r and vary its output type:

r -> a

The arrow can be written in prefix form, so the corresponding unary type constructor is ((->) r). Applying it to a gives r -> a.

Its mapping type is:

-- fmap specialized to functions:
-- (a -> b) -> (r -> a) -> (r -> b)

This is function composition. The standard instance behaves conceptually as:

-- Illustration of the existing instance; do not redefine it.
instance Functor ((->) r) where
  fmap = (.)

For example:

fmap (+1) (*2) (10 :: Int)
-- 21
 
-- Equivalent to:
((+1) . (*2)) (10 :: Int)
-- 21

Mapping transforms the result of the original function, while retaining its input. This works without a container holding a preexisting result: the result may only be computed when an input arrives.

The general capability is to turn a function a -> b into a function f a -> f b lawfully. “Apply a function inside a container” is useful for the early examples, but this broader description also covers functions and computational contexts.

8.10 The dictionary-passing connection

Each Functor instance supplies its mapping operation:

Evidence	Supplied behavior
Functor []	Map over a list
Functor Maybe	Transform a present value
Functor (Either String)	Transform the Right parameter
Functor Tree	Recursively transform node labels
Functor ((->) r)	Compose a result transformation

When the compiler sees:

fmap (+1) (Just (3 :: Int))

the context fixes f to Maybe. The compiler supplies the Functor Maybe evidence, just as it supplies Eq Int evidence for equality on integers. The numeric transformation also requires Num Int, which is a separate constraint.

A generic mapping function can receive and forward this evidence:

showInside :: (Functor f, Show a) => f a -> f String
showInside = fmap show

Here the Functor operations handle the context and the Show operations handle the elements. At the conceptual dictionary level, both kinds of evidence are implicit parameters.

There is one technical difference from a simple EqDict a record: a Functor dictionary’s fmap method must work for every pair of types a and b, not just one fixed pair. Encoding that entire method in a literal ordinary record requires higher-rank polymorphism. We do not need that extension to use or define the instances above.

8.11 Infix mapping with <$>

<$> is an infix synonym for fmap:

(<$>) :: Functor f => (a -> b) -> f a -> f b

Thus these expressions agree:

fmap (+1) (Just 3) -- Just 4
(+1) <$> Just 3    -- Just 4
 
show <$> ([1,2,3] :: [Int])
-- ["1","2","3"]

You will encounter this notation frequently when reading Haskell code. It changes how the application is written, rather than adding a different mapping capability.

8.12 What Functor alone cannot express

Suppose we have two optional values:

x :: Maybe Int
x = Just 3
 
y :: Maybe Int
y = Just 5

Mapping an ordinary unary transformation works. But adding the two values exposes a limitation:

fmap (+) x
-- Has type Maybe (Int -> Int)

Because (+) is curried, mapping it over x partially applies addition and leaves a function inside Maybe. That result is not an ordinary function, so we cannot apply it to y by writing fmap (+) x y.

Functor supplies no operation for applying that contextual function to another contextual argument. More powerful interfaces can add that capability:

Interface	Capability
Functor	Map an ordinary function over one context
Applicative	Apply a contextual function to a contextual argument, combining independent contextual inputs
Monad	Sequence computations when a later contextual computation depends on an earlier result

You can always pattern-match on a particular type such as Maybe and combine values by hand. The limitation is what the generic Functor interface provides. Part 9: Applicative Functors and Monads derives Applicative from this question, then introduces bind for dependent computations.

8.13 A first glimpse of category theory

The name functor comes from category theory. A category has objects, arrows between objects, identity arrows, and a composition operation. Composition must be associative, and identity arrows must act as identities.

For an initial programming intuition, picture objects as types and arrows as functions. A functor $F$ maps types to types:

$$A⟼F(A),$$

and maps functions to functions:

$$(g:A\to B)⟼F(g):F(A)\to F(B).$$

In our Haskell interface, applying a type constructor describes the first mapping; fmap describes the second. The two laws require preservation of identities and composition:

$$F({\mathrm{id}}_A)={\mathrm{id}}_{F(A)},$$ $$F(g\circ h)=F(g)\circ F(h).$$

This picture explains the programming interface without making category theory a prerequisite. It is a simplified interpretation: Haskell’s partial functions, bottom values, and evaluation behavior mean that a precise categorical model needs more care than simply declaring that all Haskell types and expressions form the category of sets and total functions.

8.14 Exercises

1. Find the result and type

fmap show (Just (5 :: Int))

Show solution

Just "5" :: Maybe String

show changes an Int into a String; Maybe remains the surrounding type constructor.

2. Map over Left

fmap (+1) (Left "error" :: Either String Int)

Show solution

Left "error" :: Either String Int

The Functor (Either String) instance maps over the Right parameter. This value contains only a Left payload, which remains unchanged.

3. Infer the most general type

twiceMap g = fmap g . fmap g

Show solution

twiceMap :: Functor f => (a -> a) -> f a -> f a

Both occurrences use the same g. Its output must fit its own input, so g is an endomorphism, a -> a. Both maps use the same surrounding constructor f.

4. Implement mapping with a fixed tag

data Tagged e a = Tagged e a
  deriving (Show)

Write Functor (Tagged e).

Show solution

instance Functor (Tagged e) where
  fmap g (Tagged tag value) = Tagged tag (g value)

The first parameter, e, is fixed. Mapping preserves the tag and transforms the last parameter.

5. Check the identity law

data Box a = Box a
 
instance Functor Box where
  fmap g (Box x) = Box (g x)

Does identity hold?

Show solution

For a constructed value:

fmap id (Box x)
  = Box (id x)
  = Box x

Yes: the implementation keeps the constructor and applies identity to its payload. The matching composition argument reduces both routes to Box (g (h x)).

Concept	Meaning
Type constructor	Produces a type when given its type arguments
Kind	Classifies types and type constructors
Functor f	Supplies lawful mapping for a unary type constructor
fmap	Transforms (a -> b) into (f a -> f b)
<$>	Infix spelling of fmap
Identity law	Mapping identity leaves the input unchanged
Composition law	Mapping composition agrees with composing mappings

The central signature is:

fmap :: Functor f => (a -> b) -> f a -> f b

f selects the context, a and b select the element types, and the instance supplies the lawful mapping operation. Lists make this concrete; optional values, trees, and functions show how far the same interface reaches.

Adapted from the complete Block 8 in the original GPT tutorial.

← Previous: Type classes and dictionary passing · Series · Next: Applicative functors and monads →