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).¹

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² 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³ 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.⁴ 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⁵ 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).⁶

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).⁷

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).