dooygoy

Posted on

# Day 87 :: Haskell Holmes tells Watson how to curry sheep

Watson: Sherlock, I've been meaning to ask you something about pure functions. How do you define these functions, I mean I understand that functions and function types seem to be like morphisms, ephemeral entities that transform data like abstract ideas, a structure describing a pure relation, like `f :: e -> e`, a computational context into another kind of context, at least the higher order functions do that, the ones that take functions as arguments which take functions as arguments...

Holmes:... But Watson all Haskell functions take functions as arguments, it's actually quite simple, we pass functions to one another and solve our problems, the more a problem seems complicated so we call and combine more complex functions, by complex I mean appropriate for that specific domain, or more abstract and structured. The process is somewhat dual to my deductive method, it just begins bottom up instead top down.

Listen Watson, try to follow me now and I will show you how we do that. Imagine you were to just count sheep upon some green hill, imagine yourself as a shepard counting sheep, and please Watson try not to fall a sleep. So you see a sheep, call it `a` and count one, then you call a function, call it `f`, which adds numbers. How does it add numbers? Well it is defined by a method you could say, like a method that describes a typeful operation, `(+) :: Num a => a -> a -> a`. Now this function adds numbers, it is a method to add things. If you observe the method carefully you will see that the plus sign, `(+)`, is constrained to an operation, defined to add numbers, all the numbers which belong to a whole class of number, so `(+) :: Num a` would mean just that. The rest of the declaration says that the plus function takes an `a` variable and returns a variable `a` and then returns another variable `a`, more correctly said a plus function takes a variable and returns a plus function that takes a variable and returns the result. We can visualise this as `(+) :: Num a => a -> (a -> a)`. Notice the beauty in the fact that plus is defined over numbers and yet we can use it to count sheep, how great is that?! Now forget all that mambo and remember we just saw the first sheep and we have an idea of a number, number `1`, now what do we do?

Watson: Well we look at some other sheep, preferably the one next to it and count that one as two.

Holmes: That's brilliant Watson, please fetch me some tea from the replicator! Tea Earl Grey, hot! Well Watson, that is true but try to look beyond, try to abstract away the whole process of counting, it makes no difference that we are counting the sheep next to that first one as number two, and also Watson, there is something dark and sinister happening here. Imagine that you are an idiot, a complete idiot and that you had no idea how to count, imagine that! Haha! What if we could not count?! Imagine you had no idea to count at all, could you? What would you do then?

Watson: So I have to count sheep but at the same time I cannot count, I don't have the slightest idea of how to even begin to count? I guess I would call someone who could count for me, who would know how to count? Someone like you naturally I presume?

Holmes: Well yes, but you might be taking this game a bit too far into the concrete realm, now imagine you cannot count, so as you say you would call me. Could you say you would call some function be it me or someone else to count the sheep for you? A function after all is some morphism that transforms data, it is more than just a value, it takes a value in and produces a value, it returns a value, and it always returns the same value if it is provided with the same input value. Our function is a pure function, it is defined totally over the whole space of its arguments! I mean if we provide our function two sheep it better count them one, two, equals two right? It's just now quite like that you will find out, the function will simply take one sheep and output another function which will return the one plus the second sheep. But I am getting a head of myself, like taking a head of an empty list it is too early for you to understand what is going on. Just follow along!

So to get back at our counting adventure you count one sheep and than you call me or let's say our holmes function and ask it to count for you. Now what does the holmes function do then? It simply takes the second sheep as its input and returns another holmes function that takes the third sheep as its input which then again calls another holmes function which takes the fourth sheep as its input and then again, it returns a function that takes...

Watson: But wait a minute Holmes, so who is counting? And it seems to me each iteration, each new number we have another function, replicating itself, just taking the next number in line, but still no one is counting, I mean I still do not how many sheep there is in total? Also I don't think I can handle more than one Haskell Holmes, and now you are telling me there are a bunch of them!? Which one is going to sum up the whole list of these sheep??

Holmes: No worries Watson, my replicas will vanish as soon as the calculation finishes, except if you memoize me somewhere within a cache field, then I will remain for some time until you call me again. But never mind that, we will talk about memoization some other time, it is a quite fascinating idea! So basically, we call a new function for each number we add, passing a function to a function we share information, we do not count yet, or sum these numbers why would we? After all we must collect our π first, we must collect our objects before we add them. You see if we were to begin adding these objects immediatelly we would be making destructive updates creating state along the way and tell me where is the rush, if we want to be correct, truly correct and sure in what we are doing then we must collect them all and then sum them up. It is just our mind that immediatelly sums up these numbers and because notice Watson the number itself is actually the sum of all previous numbers. Look at it, the sheep number `5` tell us not just that bit of information but that actually each number is a sum of all the previous numbers, have you noticed that? Have you?

Watson: Oh my god, so a number `10` is actually the tenth number and at the same time the sum of previous numbers? But isn't the sum of all previous numbers from one to ten, something else? `sum [1..10]` is not `10`?

Holmes: Watson that is true but you are actually playing a smart boy now, because the correct list of an unknown number of sheep would be `[sheep, sheep, sheep, sheep, sheep, sheep ...]` or to use a variable instead we have a list of things something like `[a, a, a, a, a, a, a, a, a ,a]`. Do you see the difference? Now we have lets say ten individual units, ten `a`'s which if we sum, if we add together we will get `10`, but this does not apply to your example because summing numbers from one to ten is a bit different, a more abstract situation, because you already know the numbers you got, if would be like adding one sheep then adding two sheep, then adding three sheep on that hill over there, than imagine you had four sheep over there, look there, a bit further away, then look you have five sheep over there! How would we describe this?

``````(+) [1..10]

{- let us unfold the list into its elements,
[1, 2, ,3, 4, 5, 6, 7, 8, 9, 10]

1 + (2..10)
1 + (2 + (3..10))
1 + (2 + (3 + (4..10)))
1 + (2 + (3 + (4 + (5..10))))
1 + (2 + (3 + (4 + (5 + (6..10)))))
1 + (2 + (3 + (4 + (5 + (6 + (7..10))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8..10)))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9..10))))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + (10)))))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + (10 + ()))))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + (10 + 0))))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + (9 + 10))))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + (8 + 19))))))
1 + (2 + (3 + (4 + (5 + (6 + (7 + 27))))))
1 + (2 + (3 + (4 + (5 + (6 + 34)))))
1 + (2 + (3 + (4 + (5 + 40))))
1 + (2 + (3 + (4 + 45)))
1 + (2 + (3 + 49))
1 + (2 + 52)
1 + 54
55
``````

Take a look at this beauty Watson, enjoy this linear recursive process! And mind you a list is a collection of homogeneous entities, meaning they are similar and uniquely different, you could say they have the same type...

Watson: This calculation is amazing Holmes, and just look at it, how the program expands in time and space! How did you do that? But it looks awfully difficult too. I think I can manage to process until it unfolds completely, but then how do you put the numbers together, I mean it seems this is much better suited for computers than humans, but then again this process precisely describes the whole act of counting sheep! And somehow we are fully aware of everything what is happening at every step of the way. I imagine if we merely destructively updated the state with a counter it would look much simpler and yet all the magic would be hidden away! But wait a minute, this is not quite right, how would we sum just a bunch of ones?

``````1 + (x)
1 + (1 + (x))
1 + (1 + (1 + (x)))
1 + (1 + (1 + (1 + (x))))
1 + (1 + (1 + (1 + (1 + (x)))))
1 + (1 + (1 + (1 + (1 + (1 + (x))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (x)))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (x))))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (x)))))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (x))))))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 0)))))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 1))))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + (1 + 2)))))))
1 + (1 + (1 + (1 + (1 + (1 + (1 + 3))))))
1 + (1 + (1 + (1 + (1 + (1 + 4)))))
1 + (1 + (1 + (1 + (1 + 5))))
1 + (1 + (1 + (1 + 6)))
1 + (1 + (1 + 7))
1 + (1 + 8)
1 + 9
10
``````

Watson: So a list is a collection of numbers? What is its type, a number?

Holmes: Not quite, a list is a collection of objects, which yes are similar which yes could be numbers, but could also be sheep! We used the numeral `1` to count our sheep but really Watson is that even necessary at all? I mean you could use the variable, a letter s for all I know and it would have been the same, we would still have to write 2ss, 3ss, 4ss, because when you add a letter `s`, or let's better call it a character `s` to a character `s` you get `ss` or you could also say you get two `ss`, it's just it is more convenient to use numbers, at least for now while operating on the term-level. Mind you working at the term-level is not for everybody, people get hurt here, they leak memory etc. It's gruesome and bloody!

Now tell me what type is a sheep anyway? Some kind of an animal right? A sheep is not an `Int`, or an `Integer`, right? Which means a sheep does not belong to a `Num` class of numbers, of which certain kinds of number are only instances of this large class of numbers. We have `Integer`, `Int`, but we also have `Float` and `Double` and hey you could define any number you like, I myself am intrigued by surreal numbers, I fell in love the moment I heard about these wondrous entities, they seem to encode more information within, but more on surreals some other time! Watson, please notice that the whole idea of a number comes from ordering things, after all you are aware of some order, meaning the idea that some things come before or after some things, after all how do we measure time? One second passes, two second passes, one minute...

Watson: After all what are we doing thinking about programs all the time, yes we write our cases, and explain our steps and people read our stories and follow our investigations but at the end of the day what is it that we do actually?

Holmes: You find yourself perplexed again my Watson, by the wonderful world of programs, they seem elusive, no matter how hard we try to encode these entities into our frameworks a bitter taste remains, something again to strive for, some new algorithm, but honestly aren't you bored sometimes by the..

The baby is crying, and it is time for a bath, I enjoyed this a lot, I hope you did too...