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 signature2 of this function is written as
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 Python3 there is a function
str which converts a
object to a string with a readable representation of that object. So
str to an integer will return a string with that integer as
'42'. Now given a list of integers we can
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
really do that, but we can create that function manually with the help
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
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
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.
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
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] 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 dictionaries5 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
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
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
. 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..?
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.
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[return]
list(map(str, [1,2,3]))to get the same result.
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]