☕biscuits in tea
☕ biscuits in teaProgrammingFunctors Visually↑ Top
Haskell · Programming

Functors Visually

A visual and practical introduction to fmap: transform the contents while preserving the surrounding structure.

·●●○intermediate·λ Haskell

Suppose you know how to transform an Int into a String:

label :: Int -> String
label n = "value=" ++ show n

What should happen when the integer is wrapped inside Maybe, a list or a tree? A functor lifts the transformation into the surrounding context.

Functor

A type constructor f is a functor when it provides:

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

along with the identity and composition laws.

The picture

        a  ───── f ─────▶  b
        │                 │
     wrap               wrap
        │                 │
        ▼                 ▼
      F a ──── fmap f ──▶ F b

The upper arrow transforms a plain value. The lower arrow performs the corresponding transformation without dismantling the context.

FunctorExamples.hs
fmap (+1) (Just 5)
-- Just 6

fmap (+1) [1, 2, 3]
-- [2, 3, 4]

fmap length (Right "lambda")
-- Right 6
The same pure function travels through several different structures.

A tree functor

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

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

Notice the recursion: at every leaf we transform the value; at every branch we preserve the branching pattern.

Functor identity law

For every lawful functor, fmap id = id.

Proof

For Tree, structural induction does the work. A leaf becomes Leaf (id x), which is the original leaf. For a branch, the induction hypothesis preserves both subtrees, and therefore preserves the complete branch.

Why Maybe is useful

safeHead :: [a] -> Maybe a
safeHead []    = Nothing
safeHead (x:_) = Just x

firstLength :: [String] -> Maybe Int
firstLength names = fmap length (safeHead names)

No manual case analysis is required merely to transform the successful value.

Exercisemedium

Implement Functor for Pair a, where only the second type parameter varies:

data Pair a b = Pair a b
Reveal solution
instance Functor (Pair a) where
  fmap f (Pair fixed value) = Pair fixed (f value)

The first field belongs to the fixed part of the structure; only b is transformed.