# Making your brain tingle: Functions as functors

# Making your brain tingle

I love the feeling you get, when during learning new concepts suddenly everything starts to fall into place and ideas which seemed hard to grasp become intuitive. I’d like to describe the feeling of such moments as “tingling of the brain”.

One area which makes my brain tingle on a regular basis is the combination of Haskell and category theory. The topic of this blog post is one simple example: I’m going to show a way of thinking of functions as functors which, at least to me, makes it intuitive.

Even the topic at hand sounds (and surly is) a bit esoteric and theoretical, not much prior knowledge should be needed to follow. I’ll use Haskell in some examples, but its rather simple code and I’ll throw some Python in for the masses, so one should hopefully be able to grasp the essence without learning Haskell, (which I would nevertheless recommend).

# What are Functors?

Functors are a concept from category theory, they are mappings between objects preserving structure, which means that not only the objects them selves are mapped but any morphisms between these objects are mapped, too.

Without any basic knowledge of category theory this definition is not
of much help, so let’s see, what this means in terms of programming:
when looking at computer languages as categories, then the objects are
types and the morphisms are functions. So we have a bunch of types,
e.g. integer, bool, string etc. and functions “between” them, in the
sense that a function takes an argument of one type and returns a
value of another (or the same type).^{1}

## lists are functors

A common example of an functor in programming is a list: any Type *a*
can be mapped to a *list of a* (`[a]`

in Haskell), and any function,
which takes an arguent of type *a* and returns a value of type *b* (in
Haskell the type signature^{2} of this function is written as ```
a ->
b
```

) can be mapped to a function taking a *list of a* as argument and
returning a *list of b* (`[a] -> [b]`

). A way of doing this mapping of
functions is available in many languages and generally called *map*.

For example in Python^{3} there is a function `str`

which converts a
object to a string with a readable representation of that object. So
applying `str`

to an integer will return a string with that integer as
text: `str(42)`

returns `'42'`

. Now given a list of integers we can
use `map`

to apply `str`

to every element of the list:

```
map(str, [1, 2, 3])
# returns: ['1', '2', '3']
```

It’s worth noting, that we are not really done yet, we said, that
there should be mapping of our function (`str`

in this case) to a new
function which takes and returns lists. In Python `map`

doesn’t
really do that, but we can create that function manually with the help
of map:

```
def lstr (l):
return map(str, l)
lstr([1,2,3])
# returns: ['1', '2', '3']
```

Even better, we can generalize this, so that we have a function `fmap`

which for every function `a -> b`

returns a function `[a] -> [b]`

:

```
def fmap(f):
def newf(x):
return map(f,x)
return newf
fstr = fmap(str)
fstr([1,2,3])
# returns: ['1', '2', '3']
```

in Haskell, where the (rough) equivalent of `str`

is called `show`

the
same looks like this:

```
fShow = fmap show
fShow [1, 2, 3]
-- returns: ["1","2","3"]
```

`fmap`

is already defined in Haskell for all functors, not only for lists.

## more functors

Besides lists there are many more functors: examples are trees or the
*Maybe* type in haskell, which can either hold an value of an specific
type or nothing. A value of the type `Maybe a`

can be `Just a`

or
`Nothing`

. It a functor, so our previously defined function
`fShow`

works on it, too:

```
fShow (Just 42)
-- returns: Just "42"
fShow Nothing
-- returns: Nothing
```

## a similarity

all the functors we have seen so far are very similar in one way: they
are all containers for values of a given type: `Maybe a`

is a container
for one or zero values ot type `a`

, `[a]`

is a container for an
arbitrary number of as, and trees are too, only providing a different
organisation of the values.

But there are various examples of functors which aren’t obvously
containers.^{4} One example is the topic of this article: **functions are
functors**! But are they containers?

# Functions as containers

It turns out that in a sense functions actually can be thought of as
containers. Pure functions, that is functions which don’t have any
side effects are equivalent to dictionaries^{5} in that they provide a
constant mapping of keys (the argument to the function) to values (the
return value of the function).

So any function can, at least in theory, be replaced by a lookup table (LUT), with entries for any valid input, where each entry is a pair of one possible input value and the return value.

One practical problem is, that these LUTs often would be very big,
even infinite in many cases: you need an entry for every possible
value of the function argument (which is all possible values of its
type). In case of an function only taking a *bool* as input, the LUT
would only have two entries but in case of arbitrary precision
integers it would have to have an infinite number of entries to
represent a *total function* (a function which can return a result for
every valid input).^{6}

## LUTs as functions

Lets demonstrate the idea in Haskell, we define a new data type
`LutFun a b`

which is noting but a list of pairs `(a, b)`

. It will be
used as our new, LUT based function type: a function `Bool -> String`

becomes
`LutFun Bool String`

.

In addition we need to define a way to call our functions, as Haskell
doesn’t know about them. I call it `apply`

and it takes two
arguments: the function (of type LutFun) and the argument the function
shall be applied to:

```
import Data.List
import Data.Maybe
data LutFun a b = LutFun [(a,b)]
apply :: Eq a => LutFun a b -> a -> b
apply (LutFun f) x = fromMaybe (error "Illegal input to function.")
$ lookup x f
```

Those how are not familiar with Haskell, don’t get confused by the
details: in the end `apply`

does nothing more than finding the pair
in our LutFun where the first element matches the given argument and
returning the second element. If it can’t find a matching pair an
error is created.

So, lets put it to a test. We start by defining a function `bool2str`

which takes an argument of the type *bool* and returns an *string*,
this only needs two entries in our LUT:

```
bool2str = LutFun [(True,"Yes"),(False,"No")]
apply bool2str True
-- returns: "Yes"
apply bool2str False
-- returns: "No"
```

Now for some simple arithmetic, how about a function `addOne`

which
adds one to its argument?

```
addOne = LutFun [(0,1),(1,2),(2,3)]
apply addOne 2
-- returns: 3
-- but
apply addOne 3
-- triggers an exception: Illegal input to function.
-- fortunately Haskell uses lazy evaluation, so we can
-- actually create an infinite lookup table:
addOne = LutFun $ zip [0..] [1..]
apply addOne 42
-- returns: 43
apply addOne 99999999
-- returns: 100000000 (eventualy)
```

By the way, the last example shows, that the dualism of data and functions also works the other way around: just as static data can substitute computations, computations can replace static data. In lazy evaluating languages like Haskell this is actually quite often the case: in stead of storing the complete result of an function in memory, the computation is (partly) postponed, and only the actually used elements of the result are generated on demand.

# Functions as functors

Now that we have seen, that functions are in a way containers of values, where you select one specific value by the function argument, it is no more surprising that they are functors. Lets test it:

```
-- First lets define a simple function,
-- which adds one to its argument:
addOne = (+1)
addOne 41
-- returns: 42
-- as addOne is a functor we can use our fShow on it:
addOneStr = fShow addOne
addOneStr 41
-- returns: "42"
-- or using fmap directly on the function:
fmap show addOne 7
-- returns: "8"
-- how about:
fmap (+1) (*2) 11
-- returns: 23
```

The mapping done by fmap in this case is this: fmap takes a function
`b -> c`

and returns a function `(a -> b) -> (a -> c)`

, which means,
the new function expects a function `a -> b`

as an argument and
returns a function `a -> c`

as result, so the mapped function `b -> c`

obviously acts on the result.

Given the idea of functions as containers, this comes to no surprise:
the result values of the function are the values in the key/value
pairs of our LUT. The mapped function works on these values (when you
think about it, you will see, that it wouldn’t make much sense if it
worked on the keys).^{7}

When you take a closer look, it turns out that it all boils down to
the fact, that the mapped function is actually applied to the result
of the function acting as functor. So `fmap g f x`

is simply
`g(f(x))`

. In Haskell instead of `fmap g f`

we can simply write ```
g
. f
```

where `.`

is the function combinator which can be pronounced as
“after”, so it says “apply the function *g* after the function *f* ”:

```
addOneStr = show . addOne
addOneStr 41
-- returns: "42"
-- or:
((+1) . (*2)) 11
-- returns: 23
```

So functions as functors don’t provide any new features, what a let down! But the journey was fun, wasn’t it..?

# Learn more

If you want to learn more about category theory in general or in the
context of computer programming, I highly recommend the great series
**Category Theory for Programmers** by Bartosz Milewski. You can read
it on his
Blog
or watch it as ongoing series of talks, given by him self on
YouTube.

# Please discuss

My blog now has comment feature, so I would be delighted if you leave any comment, critique or questions (which, of cause, I will try to answer).

You may ask “What’s with functions taking more than one argument (or returning more than one value)?”, that is a good question, but it is beyond the scope of this article. As a short spoiler: it is possible to convert any function taking more than one argument into a function which takes exactly one (by taking cartesian products as argument, or even better, by currying), and returning more than one value is always equivalent to returning a cartesian product. Go, google yourself or wait for me to write something on these topics (which might or might not be happening).

^{[return]}the concept of type sigantures is widely known in the world of programming, but sometimes under other names, e.g. in C it’s called “function prototypes”.

^{[return]}I’m using Python 2 in this example, in Python 3 the return type of map changed to iterable, so you would have to write

`list(map(str, [1,2,3]))`

to get the same result.^{[return]}There is a higher-level discussion if it is a good idea to use the picture of containers to explain functors. I tend to think, that this metaphor is working quite well for endofunctors as we experience them in programming languages (which is part of the motivation behind this article). But for the more general concept of functors in category theory it is indeed misleading.

^{[return]}associative arrays, maps, symbol tables or what ever you like to call it…

^{[return]}nonetheless, replacing functions by lookup tables, for at least a subset of possible input values, has been done in computer programming for ages. It is a simple optimization, where functions, which do heavy computation are the bottleneck, and the same input values are repeatedly used. Examples go from simple pre-calculated sin-tables, as they were common on 8bit systems, over “caches” of many sorts to data “baking” (pre calculating and reusing the results) in modern 3d graphics software.

^{[return]}actually functions are not only functors but profunctors, which means there

*is*a kind of functor – a contravariant functor – which operates on the argument of the function instead of the result, but in our picture that operation would be done on the argument*before*the lookup of the key in the LUT, so the key values in the LUT are still unaltered.^{[return]}