Learning programming with C, functions were a very special thing for me in my early days. Though there were
function pointers back then, didn’t use those much and I had this idea that functions are very different from data.
After being introduced to
lambdas, functions started becoming less special, with the ability to use them as first class citizens they seemed very much like data as I could pass those around like values, could create higher order functions.
After spending some time with
Haskell it became a lot more clear that functions and data aren’t very different. And by
function here I mean functions without any funny business aka pure functions. For anyone not knowing what pure functions are, they are like Matemathical functions which always return the same value for the same set of arguments.
My purpose in this post is to try explaining why functions are very much like data. The code examples will be in
Haskell but they will be simple enough to be understandable to anyone having decent programming experience.
Lets talk about pure functions a bit. What they are, how they behave etc.
Consider the following
It’s a very simple function. Takes two
Integers and return their
summation. And as you can see from the definition
it doesn’t do anything else.
Now as a optimization technique, we can decide to generate the sum of all integers (for simplicity’s sake consider they are 8 bit unsigned integers and the number of possible values for either of
y will be
2^8 or 256) and save them in a hash/table. Once we have all the values, then the function call just become a hash/table lookup. The table for the above function will look like the following.
Just to make it clear, it’s not about the optimization, don’t get caught up in that or try to judge it’s usefulness, we are trying to grow our intuition of functions, looking at functions from a different angle.
So we deliberatly only considered
8-bit integers. What about
32-bit? or whatever bit you can think of? We could still fill up our table with all possible inputs (which is infinite in extreme cases). So if we had infinite resources we could memoize all pure functions and then our programs would just have been constant(?)/super fast table/hash lookups.
Ok enough talking about optimizations. The one takeaway I would like to convey from this section is that
pure functions are very similar to hash lookups or data.
Data as functions
Lets say we have a list defined in haskell like follows
1 2 3 4
The above is a pefectly valid chunk of
Haskell code. So our list
myList is an infinite list. Do you think the runtime will dare to go ahead and generate the complete list for you? As you might have guessed correctly, it won’t. Haskell is lazylanguage by default. It doesn’t execute anything unless it’s forced to. Like on the second line we are forcing the runtime to generate the first 5 numbers from
myList using the
On a side note we can do all sorts of cool things by exploiting this behaviour of the haskell runtime. Lets look at the following fibonnacci number generator
It’s a full featured infinite fibonacci number generator, and like before we can force it to generate the first 5 fibonacci number using
take 5 fibs, we can also use it as a list, for example
fibs !! 10 will return
!! is the function to access a list value of a certain index in haskell). It’s cool and elegant, isn’t it? I won’t go ahead and start explaining how it works, but that could be the content of a future blog post.
Anyway, back to the point, though the last two examples were lists, they were actually more like functions, you force the runtime to give more values and it goes ahead, use some kind of generator to generate next values of the list to return them back.
So, lists which think of data structures, can be represted/thoght of as functions. Lets see the following hash,
It’s a simple data structure which has some data inside. But we can also think of it as function which takes a
String and return another
String and has it’s data calulated and indexed by it’s argument. You can think of
myHash['hello'] which is the way to access the value of key
hello as function call.
Function as Data, Data as function
From the above sections we can see that a function can be thought of as a container of values. You give it some kind of index (
arguments), it gives you back the result for that index.
This intuition about thinking functions as container of data helps to understand some higher level concenpts from abstract algebras like
Functors which is omnipresent everywhere once you learn to recognize them.
Hope you enjoyed it. :)