What's That Typeclass: Functor

You might already know the map function:

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

> map (\x -> x + 1) [1, 2, 3]
[2, 3, 4]

It takes a function of type a -> b and applies it to each element of a list. The elements change, but the data type storing them ([]) remains the same. In this article, we’ll call such a data type with another type inside it a context.

Transforming values inside fixed contexts is common in programming.

For example, the optional data type (Maybe) provides a context of a possibly failed computation. It can also be “mapped” by trying to apply a function to the wrapped value without changing the context.

map' :: (a -> b) -> Maybe a -> Maybe b

map' f (Just x) = Just (f x)
map' f Nothing = Nothing

> map' (\x -> x + 1) (Just 1)
Just 2
> map' (\x -> x + 1) Nothing
Nothing

This article will introduce you to Functor – a typeclass that unifies these kinds of transformations and provides common functionality for them.

After reading this article, you’ll know:

• what Functor is in Haskell;
• how to define and use your own Functor instances;
• why and where Functors are useful.

We’ll also provide a set of exercises to consolidate your knowledge.

How to generalize map

Look at the type signature of map:

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

It takes a function a -> b. Then, it uses that function to change the contents of a list.

Now, look at the type of map'. It uses the same type of function – a -> b – to change the contents of Maybe.

map' :: (a -> b) -> Maybe a -> Maybe b

The type signatures are kind of similar!

Could we have a more general function that works for many different contexts? Absolutely. It’s Haskell, after all.

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

Here’s how it works. fmap takes an a -> b function and an f a data type (a wrapped in any context f). The function is applied to what’s inside the context, and a value of type b wrapped in f is returned. The value can change, but the context remains the same.

Let’s look at a few examples:

-- Apply `reverse :: String -> String`
-- to a list of `String`s
-- to get a list of `String`s.
> fmap reverse ["abc", "def", "ghi"]
["cba","fed","ihg"]
> fmap reverse []
[]

-- Apply `show :: Int -> String`
-- to a list of `Int`s
-- to get a list of `String`s.
> fmap show [1..3]
["1","2","3"]
> fmap show []
[]

-- Apply `(+1) :: Int -> Int` 
-- to `Maybe Int`
-- to get `Maybe Int`.
> fmap (+1) $ Just 1
Just 2
> fmap (+1) Nothing
Nothing

-- Apply `(> 0) :: Int -> Bool` 
-- to `Maybe Int`
-- to get `Maybe Bool`.
> fmap (> 0) $ Just (-1)
Just False
> fmap (> 0) $ Just 1
Just True
> fmap (> 0) Nothing
Nothing

-- Apply `chr :: Int -> Char`
-- to a pair `(a, Int)`
-- to get a pair `(a, Char)`.
-- Note that only the second value is mapped.
> fmap chr (65,65)
(65,'A')
> fmap chr ('a',97)
('a','a')

As you may have guessed, map is just a synonym of fmap for lists. But it can do much more. With fmap, we can do actions inside data types like [], Maybe, Either a, ((,) a), and others.

Of course, we cannot provide an implementation of fmap that works for all contexts. Instead, to use it on a data type, that type needs to have an instance of the Functor typeclass. As we’ll see, Functor is the thing that provides the implementation.

The Functor typeclass

What’s the Functor typeclass? Let’s ask GHCi.

> :info Functor
type Functor :: (* -> *) -> Constraint
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}

Functor in Haskell is a typeclass that provides two methods – fmap and (<$) – for structure-preserving transformations.

To implement a Functor instance for a data type, you need to provide a type-specific implementation of fmap – the function we already covered.

For most common data types, instances of Functor are already implemented. For your own data types, you’ll need to define them yourself.

data Option a = Some a | None

instance Functor Option where
  fmap f (Some a) = Some (f a)
  fmap f None  = None

We’ll cover how to do this in more detail later.

What can be a functor?

There’s two things that limit what you can implement a Functor instance for: the kind signature of Functor and its laws.

Kind signature of Functor

The kind of Functor is (* -> *) -> Constraint, which means that we can implement Functor for types whose kind is * -> *. In other words, we can implement Functor for types that have one unapplied type variable.

For example, Maybe and [] take one type variable. Hence their kind is * -> *, and there’s a straightforward Functor implementation for them.

> :kind Maybe
Maybe :: * -> *

Int has no type variables, and its kind is *, so you cannot create a Functor instance for it.

> :kind Int
Int :: *

Either takes two type variables, so it’s kind is * -> * -> *. But if we apply it once, we can make the kind be * -> *.

> :kind Either
Either :: * -> * -> *
> :kind Either String
Either String :: * -> *

Therefore, there is a valid Functor instance for an applied Either – instance Functor Either a, where a signifies any variable that could be applied.

Functor laws

Some of Haskell typeclasses have laws – conditions that instances have to meet. Usually, these laws come from the math concept of the same name.

A functor is a mapping in category theory. Hence, we need fmap to adhere to the following laws.

1. Identity

   fmap id x == id x – applying id function to the wrapped value changes nothing.

   Example:

   fmap id (Just 1) == id (Just 1) == Just 1

2. Composition

   fmap f (fmap g x) == fmap (f . g) x – applying fmaps sequentially is the same as applying fmap with the composition of functions.

   Example:

   fmap (+1) (fmap (*2) (Just 1)) == fmap ((+1) . (*2)) (Just 1) == Just 3

You may wonder why you should follow these laws. The answer is simple – if the instance doesn’t meet these conditions, the typeclass’ methods won’t work as expected. You might run into unpredictable behaviour and confuse people that work with your code as well.

Laws aren’t enforced by the compiler, hence you need to ensure their correctness yourself. It may be a bit difficult at the beginning, but after a couple of instances, it will start to feel natural.

There is a tool that can verify whether an instance follows laws – QuickCheck. It checks properties by random testing. You can provide it a property the code needs to satisfy (a typeclass law, in our case), which is then checked on a large number of randomly generated values. You may look at the “Checking the laws” section of this article as an illustration.

The (<$) operator

fmap is all you need to define a Functor instance. However, the (<$) operator is worth looking at too.

Here’s the type signature of (<$):

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

The operator takes a value of type a, a value of type b packed in a functor f – f b – and produces a functor f a. Basically, the operator packs the first argument’s value in the context of the second argument, throwing away the second value.

Now, a little exercise. Let’s try to guess the definition of (<$) by using the provided description and the following examples.

-- replace an `Int` value
-- inside `Maybe Int`
-- with a `String`
> "abc" <$ Just 123
Just "abc"
> "abc" <$ Nothing
Nothing

-- replace each element
-- of the list `[Int]`
-- with an `Int`
> 1 <$ []
[]
> 1 <$ [0]
[1]
> 1 <$ [1..5]
[1,1,1,1,1]

Pay close attention to the list examples. y <$ [x1, x2, x3] results in [y, y, y] not [y] since the list has many values inside and not one. Each element of the list is transformed instead of the value being wrapped in [].

So, what do you think is the default definition of (<$)?

x <$ f = fmap (const x) f

Now that we’ve seen the basic components of Functor, it’s time to create our own instance of this typeclass!

How to implement a Functor instance

Let’s see how you can implement your own instance of Functor. We’ll use the NonEmpty data type as an example.

NonEmpty' represents a list with at least one element. It has two components: a must-have head a and a tail [a], which might be empty.

data NonEmpty' a = NonEmpty'
  { neHead :: a
  , neTail :: [a]
  }

To define the Functor instance, we need to implement fmap.

We define it by pattern matching on the head and the tail of the non-empty list. Applying f to the head x takes care of it, but what about the tail?

Note: to be able to write the type signature of fmap in an instance definition, you need to use the InstanceSigs extension.

instance Functor NonEmpty' where
  fmap :: (a -> b) -> NonEmpty' a -> NonEmpty' b
  fmap f (NonEmpty' x xs) = NonEmpty' (f x) ??

The tail is a regular list. And fmap for lists is already defined, so we can just use that:

instance Functor NonEmpty' where
  fmap :: (a -> b) -> NonEmpty' a -> NonEmpty' b
  fmap f (NonEmpty' x xs) = NonEmpty' (f x) (fmap f xs)

However, let’s explore the implementation to understand the mechanics of fmap better.

instance Functor [] where
  fmap :: (a -> b) -> [a] -> [b]
  fmap f x:xs = f x : fmap f xs
  fmap _ []   = []

In fact, it follows the same principle – splitting a list on head and tail and calling the function recursively. On each iteration, we apply f to the head and call fmap with the tail of the list. In the end, we need to cover the empty-list case – “fmapping” an empty list gives an empty list.

And it’s done! You’ve just seen how to define an instance of Functor. If you wish to practice more, the exercise section has an additional implementation exercise for you to try.

Functor is not always a container

There is one noteworthy fact about Functor – it’s not always a container. The laws of Functor permit some rather wild implementations. For example, functions are functors too!

But is there any data type that corresponds to functions? The answer is yes. It’s (->).

> :info (->)
type (->) :: * -> * -> *
data (->) a b

(->) is parametrized with two types – (->) a b. In other words, it is a -> b – a function with one argument.

We know that Functor can only be implemented for types with the * -> * kind. Unfortunately, the kind of (->) is * -> * -> *. It doesn’t satisfy the Functor instance in this form because a Functor can only have one type argument.

Hence, it’s required to apply it once, as we do with Either a or ((,) a). In the (->) case, it means providing the function argument’s type – (->) a or a -> (the latter is not valid syntax in Haskell, though).

For example, functions with the following type signatures have Functor instances:

Int -> a
String -> a
(Char, Int) -> a
[Int] -> a

So we’ve found out what functions can be functors and what data they match. The next question is – what does it mean to fmap a function? Intuitively, it’s about changing the function, i.e., the action it performs. But what is the fixed context here?

Let’s construct the type definition of fmap for a one-argument function. For an arbitrary Functor f, fmap is:

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

The type of our data is (->) c. Therefore, we need to replace f t by (->) c t or c -> t. Consequently, the type signature is:

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

Now we can see that the fixed context corresponds to the type of function’s argument c. And the value being modified is the function’s return type – we go from a to b with the help of the a -> b function.

All in all, fmap for functions transforms what the function returns while keeping the input unchanged! Does that look familiar to you?

> :t (.)
(.) :: (a -> b) -> (c -> a) -> c -> b

Cool! fmap for Functor is just the composition of functions.

Here’s the ((->) a) instance implementation:

instance Functor ((->) a) where
  fmap = (.)

In conclusion, let’s make sure fmap is (.) for one-argument function a -> b with the example below:

-- fmap :: (Int -> Int) -> (Int -> Int) -> Int -> Int
> fmap (+1) (*2) 2
5
> (+1) . (*2) $ 2
5

It’s uncommon to consider a function a Functor in Haskell. In fact, it’s more of a fancy case. However, you’ll not be puzzled when you come across this magical and strange usage of fmap in the future!

Why is Functor useful?

In general, Functor is not an extraordinary typeclass. Its methods are easy to grasp and to implement.

Nevertheless, a Haskell project can hardly do without a couple of Functor instances. It enables one to do transformations on the wrapped type without knowing anything about the wrapper, and that’s very beneficial.

Moreover, Functor is a solid basis and the predecessor of the Applicative typeclass, which further leads to Monad. The latter is a famous and widely used typeclass in Haskell. Understanding it will give you a considerably greater command of the language.

Conclusion

In this article, we have covered the Functor typeclass: what it is, where it can be used, and how to implement your own instances of Functor. It’s a part of the What’s That Typeclass series, where we introduce readers to commonly used Haskell typeclasses.

If you want to read more articles from Serokell, be sure to follow us on Twitter or subscribe to the newsletter via the form below.

And finally, if you see anything that’s wrong with the article or if there’s something you don’t understand, you’re welcome to submit an issue in our GitHub repo – we’d appreciate that greatly!

Exercises

1. Implement Functor for binary search trees.

   data BinarySearchTree a
     = Branch (BinarySearchTree a) a (BinarySearchTree a)
     | Leaf
   

   Expected behaviour:

   > bst = Branch (Branch (Branch Leaf 1 Leaf) 2 (Branch Leaf 3 Leaf)) 4 Leaf
   > (+1) <$> bst
   Branch (Branch (Branch Leaf 2 Leaf) 3 (Branch Leaf 4 Leaf)) 5 Leaf
   

   Solution

   instance Functor BinarySearchTree where
     fmap :: (a -> b) -> BinarySearchTree a -> BinarySearchTree b
     fmap _ Leaf                     = Leaf
     fmap f (Branch left node right) = Branch (fmap f left) (f node) (fmap f right)
   

   ---

2. Implement (<$) for Maybe a.

   Solution

   (<$) :: a -> f b -> f a
   _ <$ Nothing  = Nothing
   x <$ (Just y) = Just x
   

   ---

3. Implement a function that converts strings to upper case (toUpperString :: String -> String) without using toUpper.

   Expected behaviour:

   > toUpperString ""
   ""
   > toUpperString "abc"
   "ABC"
   

   Assume that the input is correct, i.e., all characters are lowercase English letters.

   Solution

   caseDiff = ord 'a' - ord 'A'
   
   -- applying `fmap`s sequentially
   toUpperString str =
     fmap chr .
     fmap (subtract caseDiff) .
     fmap ord $
     str
   
   -- applying `fmap` with the composition of functions
   toUpperString str = fmap toUpperChar str
     where
       toUpperChar = chr . subtract caseDiff . ord
   

   ---

4. Prove that the instance Functor ((->) a) we discussed previously follows the identity and composition laws.

   Identity: fmap id == id.

   Composition: fmap f . fmap g == fmap (f . g).

   Solution

   See the Functor laws for functions paragraph

   ---

Serokell provides Haskell programming services and has extensive knowledge in crafting tailored software solutions. We are delighted to solve your business challenges, no matter the field and complexity of the task. Let’s connect and have a chat!