0102: Email Tutorials – AFP 5 — Functors

AFP 5 — Functors

📚 Table of Contents

1. Email 1 – The Big Question: Pure or Impure?
2. Email 2 – Why “Effects” Matter in Real Programs
3. Email 3 – A Pattern Hiding in Plain Sight: inc and square
4. Email 4 – Abstracting the Pattern: Rediscovering map
5. Email 5 – Generalising Beyond Lists: Why We Need Functors
6. Email 6 – The Functor Typeclass: fmap and Type Constructors
7. Email 7 – Functor Instance #1: Lists ([])
8. Email 8 – Functor Instance #2: Maybe (Propagating Failure)
9. Email 9 – Functor Instance #3: A Binary Tree
10. Email 10 – Why Functors Are Useful: One Name, Many Structures
11. Email 11 – The Superpower: Generic Functions for Any Functor
12. Email 12 – Functor Laws: What Must Always Be True
13. Glossary of Terms
14. Quiz Questions (Table Format)
15. Quiz Options (Table Format)
16. Next Steps and Quiz Link

1. Email 1 – The Big Question: Pure or Impure?

This lecture starts with a simple but deep question: should programs be pure or impure? In programming terms, pure means your programs behave like mathematical functions: they take inputs, produce outputs, and don’t secretly interact with the outside world in the middle. Impure means programs can perform side effects like reading input, writing output, mutating state, or throwing exceptions.

This question matters because it shapes how you write code, test code, and reason about correctness. Pure code is easier to reason about and refactor safely, because “same input ⇒ same output” becomes a reliable mental rule.

2. Email 2 – Why “Effects” Matter in Real Programs

Even if purity is beautiful, real software must interact with the world:

• read user input
• write files
• call APIs
• handle failures
• manage state

So the real goal is: combine purity’s reasoning benefits with effectful programming. The lecture hints at where this is going: monads are the course’s answer (coming later). Functors are a key stepping stone because they teach you how to structure computations inside containers and contexts.

3. Email 3 – A Pattern Hiding in Plain Sight: inc and square

The lecture uses two list functions to expose a repeated programming pattern.

✅ Increment every element

inc :: [Int] > [Int]
inc []     = []
inc (n:ns) = (n + 1) : inc ns

✅ Square every element

square :: [Int] > [Int]
square []     = []
square (n:ns) = (n * n) : square ns

These look different, but structurally they are the same:

• base case: empty list maps to empty list
• recursive case: transform head, recurse on tail

That “same shape, different headtransform” is exactly the signal that abstraction is possible.

4. Email 4 – Abstracting the Pattern: Rediscovering map

Once you spot the pattern, you extract it into a single reusable tool: map.

map' :: (a > b) > [a] > [b]
map' f []     = []
map' f (x:xs) = f x : map' f xs

Now the original functions become instances of the pattern:

inc2 :: [Int] > [Int]
inc2 = map (+1)

square2 :: [Int] > [Int]
square2 = map (\n > n * n)

This is the lecture’s first big theme: abstracting common recursion patterns.

5. Email 5 – Generalising Beyond Lists: Why We Need Functors

The next leap is: mapping isn’t just for lists. You often want to “map over”:

• optional values (Maybe)
• trees
• other data structures that “contain” values

So the lecture generalises the idea: a functor is anything you can map over.

6. Email 6 – The Functor Typeclass: fmap and Type Constructors

Haskell captures “things you can map over” using a typeclass:

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

Key idea: f is not a normal type like Int. f is a type constructor (a parameterised type), like:

• []
• Maybe
• Tree

So fmap means:

“Given a function a > b, transform values inside an f a to get an f b, without destroying the structure.”

7. Email 7 – Functor Instance #1: Lists ([])

Lists are the easiest functor: fmap is just map.

instance Functor [] where
  fmap = map

So these are equivalent:

map  (+1) [1,2,3]
fmap (+1) [1,2,3]

8. Email 8 – Functor Instance #2: Maybe (Propagating Failure)

Recall the Maybe type:

data Maybe a = Nothing | Just a

Its functor instance:

instance Functor Maybe where
  fmap g Nothing  = Nothing
  fmap g (Just x) = Just (g x)

Meaning:

• If computation “failed” (Nothing), mapping keeps it failed.
• If computation succeeded (Just x), mapping transforms the value.

GHCi demos

fmap (+1) Nothing
 Nothing

fmap (*2) (Just 3)
 Just 6

9. Email 9 – Functor Instance #3: A Binary Tree

Define trees with values at leaves:

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

Functor instance:

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

This preserves shape and transforms contents.

Example

fmap even (Node (Leaf 1) (Leaf 2))
 Node (Leaf False) (Leaf True)

10. Email 10 – Why Functors Are Useful: One Name, Many Structures

Two big benefits from the lecture:

1. Same name for the same idea Instead of mapList, mapMaybe, mapTree, you use fmap everywhere. When you see fmap, you immediately read: “mapping inside something”.

2. A shared interface enables reusable tools Once many types are functors, you can write helper functions once.

11. Email 11 – The Superpower: Generic Functions for Any Functor

The lecture’s punchline: the old “increment everything” can be made fully generic.

incF :: Functor f => f Int > f Int
incF = fmap (+1)

Now it works on lists, Maybe, and trees:

incF [1,2,3]
 [2,3,4]

incF (Just 1)
 Just 2

incF (Node (Leaf 1) (Leaf 2))
 Node (Leaf 2) (Leaf 3)

This is a major mindset shift: write programs that target capabilities (typeclasses), not concrete datatypes.

12. Email 12 – Functor Laws: What Must Always Be True

A proper functor must obey two laws:

1) Identity

fmap id = id

2) Composition

fmap (g . f) = fmap g . fmap f

These laws are why you can refactor confidently: mapping “behaves like mapping” everywhere, not just in your examples.

📘 Glossary of Terms

Pure Language A language where programs behave like mathematical functions (no side effects). Impure Language A language where programs can perform side effects directly (I/O, state, exceptions). Side Effect Any interaction beyond returning a value (printing, reading input, mutation, exceptions). HigherOrder Function A function that takes a function as an argument and/or returns a function. Map A function that applies another function to each element of a list. Functor A typeclass for structures you can map over with fmap. Type Constructor A parameterised type like Maybe or [] or Tree. fmap The functor mapping function: transforms values inside a structure. Shape Preservation fmap changes values but keeps the outer structure (list length, tree shape, etc.). Functor Laws Rules (identity, composition) that make functors consistent and predictable.

📖 Recommended Reading

Buy Book

🎓 Final Step: Quiz & Progress Badge

Start Quiz (Haskell 18 – Functor)