loading...

Basics of Functor in Haskell

aibhstin profile image Aibhstin ・4 min read

Continuing with the discussion of Haskell's typeclasses, Functor is next on the list. Whereas Monoid and Semigroup were both abstractions of algebraic structures, a Functor is an abstraction of a mapping from one object to another (It's worth mentioning that 'object' here is used in the way it is used in category theory). Let's have a look at what GHCi tells us about Functor:

GHCi> :i Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}

As GHCi has helpfully told us, all we need to define a valid instance of Functor for a type is to define the fmap function. This function needs to take an argument that maps a value of type a to a value of type b and a parametric type f holding a value of a and returns a value of type b in the parametric type f.

What's going on with (f :: * -> *)? It looks like a type signature for a function, but with little stars instead of types. This is a kind signature, not a type signature. You can inspect kinds in GHCi:

GHCi> :k Int
Int :: *
GHCi> :k String
String :: *
GHCi> :k []
[] :: * -> *
GHCi> :k Maybe
Maybe :: * -> *

We can see that parametric types have different kind signatures to 'regular' types. The star can be thought of as a representation of a type. Just like a function of type (a -> b) requires a value of type a to produce a regular value in return, a parametric type of kind (* -> *) requires a type of kind * to produce a type of kind *. Kinds are really interesting, and I plan on writing a post just for them soon :)

You can think of fmap as lifting a value from a certain algebraic data structure, applying it to a function, and lowering the result back into the original data structure. The function only touches the value within the structure, but leaves the structure completely unchanged.

Let's take a list of integers and add 5 to all of them using fmap:

GHCi> fmap (+5) [1, 2, 3]
[6, 7, 8]

or, alternatively

GHCi> (+5) <$> [1, 2, 3]
[6, 7, 8]

(The <$> operator is simply an infix version of fmap)

On a list, fmap and map are essentially the same. The difference is that map only works on lists, whereas fmap works on any structure. For example, the Maybe type:

GHCi> (+5) <$> Just 5
Just 10
GHCi> (+5) <$> Nothing
Nothing

The concept is the exact same as with lists, the value is applied to the function without affecting the structure. Applying any function to Nothing with fmap will always result in Nothing. Even though Nothing looks like a nullary data constructor like True or False, it actually still carries a phantom type parameter.

GHCi> (+5) <$> Nothing
Nothing
GHCi> :t it
it :: Num b => Maybe b

We can see that even though the Nothing data constructor doesn't seem to hold any parameterized type on the surface, inspecting the type shows us that it is indeed still there.

Either and Tuple

Both Either and Tuple have instances of Functor. But how do these instances work? Let's remind ourselves of the type signature of fmap:

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

But Either is a parametric type that can take two, potentially different types in two different data constructors. Let's look at some examples:

GHCi> (+5) <$> Right 5
Right 10
GHCi> (+5) <$> Left 5
Left 5

It works as expected with the Right data constructor, but it does nothing to the value in the Left constructor. Why is this?

Firstly, observe the type definition of Either:

Either a b

The type a is considered to be part of the structure of Either. As we know, fmap must leave the structure unchanged. We can see this more clearly here:

GHCi> :i Either
. . .
instance Functor (Either a)
. . .

The type a is included as part of the structure in the definition for the instance of Functor.

What about tuples then?

GHCi> (+5) <$> (1, 2)
(1, 7)

Here the value on the left is being left unchanged. The reason is much the same: as both values can be of different types, then the type of the value to the left is included as part of the structure of the type. In Haskell, it is completely invalid to have a function (a -> b) that could be applied to two separate types in a tuple.

Functor laws

Functors in Haskell must obey the Functor laws.

Law #1: The Law of Identity

Mapping id over a type structure must yield the same result as applying id to the structure in its entirety.

-- fmap id == id
GHCi> fmap id $ Just 5
Just 5
GHCi> id $ Just 5
Just 5

Law #2: The Law of Composition

If we map the composition of functions f and g over a structure, we must get back the same result as if we had composed the mapping of f and the mapping of g independently.

-- fmap (f . g) == fmap f . fmap g
GHCi> fmap ((+5) . (*2)) $ Just 5
Just 15
GHCi> fmap (+5) . fmap (*2) $ Just 5
Just 15

The laws of identity and composition for functors MUST be obeyed whenever you define your own instances of Functor. Remember, the Haskell compiler won't stop you violating these laws, so it is your responsibility and your responsibility alone to ensure they are followed. These laws are vital to ensuring you have valid instances of functor.

Structure within Structure

What if you have a value you want to apply to a function, but it's nestled inside a structure, that is itself inside of a structure? You simply need to compose fmap!

GHCi> (fmap . fmap) (+5) $ Just (Right 5)
Just (Right 10)




Key takeaways

  • Functor abstracts out the common pattern of mapping between two algebraic objects.
  • Fmap lifts a value out of some type structure and applies it to a function, but leaves the structure completely unchanged.
  • Instances of functor must follow the law of identity and the law of composition.
  • You can compose fmap with fmap to lift over values in nestled within multiple layers of structure.

Posted on by:

aibhstin profile

Aibhstin

@aibhstin

I'm an Ethical Hacking & Cybersecurity student and a Haskell programmer.

Discussion

markdown guide
 

Thanks for the article bit I think there are some misuse terms here

Functor abstracts out the common pattern of mapping between two algebraic objects

Functor is a map between categories. Map between objects is jus a function.

You can think of fmap as lifting a value from a certain algebraic data structure

There is no requirement for the structure to be algebraic. Algebraic structure is a set + binary closed operation over set. You don't need to have such in order to use a Functor. The reality is that you can use any function which transform structure A to B in category X and use the same function in category Y, Functor is kind a portal between category X and Y

If you are interested I have started some series about algebraic structures.

 

Hi, I've corrected the usage of terms in the post, thank you for pointing them out!

I've started reading your posts on algebraic structures also. The examples in different language are really helpful

 

Thanks for being open-minded. If you see issues in my articles please don't hesitate to say that.