Functor

fmap

A functor is anything you can map over. The class has one method, and the method transforms what is inside without changing the shape:

-- the standard library defines it as: -- class Functor f where -- fmap :: (a -> b) -> f a -> f b fmap (+1) (Just 1) -- Just 2 fmap (+1) [1,2,3] -- [2,3,4] fmap (+1) Nothing -- Nothing

The same call works for a list, a Maybe, and any tree, because the class hides the traversal. That is the first place where a type class saves real code.

The two laws

An instance must obey two rules, or code that relies on fmap starts to behave strangely. The compiler does not check them, so the responsibility is yours:

-- identity fmap id (Just 3) == Just 3 -- True -- composition fmap (negate . (*2)) (Just 3) == fmap negate (fmap (*2) (Just 3)) -- True

The laws say that mapping does nothing extra: no elements are added, dropped, or reordered. A type that violates them is a container of a different kind, and the name Functor is then a lie.

An instance for your type

The tree from lesson 28 becomes a functor by applying the function to every stored value. The recursion follows the type:

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

Two lines, and the tree gains every function that works on functors. The instance is a proof that the shape is preserved: the constructors match one for one.

Why the shape matters

The f in the class stands for a type constructor that still needs one argument, not for a finished type. That is why the class takes f a:

class Wrapper f where wrap :: a -> f a -- correct: a container waiting for its element type instance Wrapper Maybe where wrap = Just -- wrong: Maybe Int is a finished type instance Wrapper (Maybe Int) where wrap = Just

Kind.hs:8:19: error: [GHC-83865] • Expected kind ‘* -> *’, but ‘Maybe Int’ has kind ‘*’ • In the first argument of ‘Wrapper’, namely ‘(Maybe Int)’ In the instance declaration for ‘Wrapper (Maybe Int)’ | 8 | instance Wrapper (Maybe Int) where | ^^^^^^^^^

The second form is rejected, because a functor must work for every element type at once. That restriction is what lets fmap have such a general signature.

The code on this page was run with GHC 9.10.3 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev