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