Prasenjit Kumar Nag a.k.a Joy

A Developers Adventure in Coding

Function as Data, Data as Function

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 closures and 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.

Pure functions

Lets talk about pure functions a bit. What they are, how they behave etc.

Consider the following add function

add :: Int -> Int -> Int
add x y = x + y

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 x or 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.

x y sum
0 0 0
0 1 1
0 2 2
.. .. ..
256 256 512

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 16-bit?, 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

myList :: [Int]
myList = [1..]

firstFive = take 5 myList -- returns [1,2,3,4,5]

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 take function.

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

fibs = 0 : 1 : zipWith (+) fibs1 (tail fibs1)

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 55 (!! 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,

myHash = { 'hello' => 'world', 'name' => 'John' }

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