One of the most useful things that you encounter all the time in programming is applying the same principle on every number in a sequence.

For example, sometimes we have a list of numbers: [1,2,3] and we want to construct the list of the squared numbers from the previous sequence: [1*1,2*2,3*3] = [1,4,9]. This means that we can abstract a little and observe that we apply the same function (the square function) on every element of our list.

That is an important remark, because instead of the square function (f(x) = x^2 for every number x – integer, rational etc.) we could have a more complicated function. For example, we could define f to be the second degree function f(x) = x^2 + 2, or a function defined by another function, etc.

So, what we’ve done basically was to map on every element of the list [1,2,3] the function f(x) = x^2 and we obtained the list [1,4,9]. Mathematically speaking, we defined map f :: [a] -> [b] in this way:
map f [a1,a2,…,an] = [f(a1),f(a2),…,f(an)], where f should be, obviously, a function f::a->b.

But how can we design the function map in such a way that a machine could compute its values?

We’ll see just in a moment one of the most important principles behind computability: recursion.

The “snake” technique

When we have a sequence of objects, (for exemplification, we’ll look at a sequence of numbers), we are usually imagining something like this:

This sequence can be seen in two parts: 1 — [2,3,5,9], where:
– 1 is the “head” of the sequence (“snake”)
– [2,3,5,9] is the tail of the sequence

In Haskell, this is simple enough to implement, we have already the primitive functions head, with head [1,2,3,5,9] = 1. and tail, with tail [1,2,3,5,9] = [2,3,5,9].

When we already extracted the head of the snake, we can apply the function f on it: f(1) and put it in a list: result = [f(1)].

Then we must repeat the snake procedure on the remaining tail: [2,3,5,9]
– head is 2
– tail is [3,5,9]

We apply f(2) and introduce it in the restul list: result = [f(1),f(2)].

What happens when the tail is empty, like in the singleton list [9]? Here, we have:
– head is 9
– tail is the empty list, by convention written like this: []

Well, in this moment the snake procedure stops and we have computed result = [f(1),f(2),f(3),f(5),f(9)]

Practically, the basic recursion procedure here is to split a list into its head and its tail, apply the function on the head, put this in the result list, and continue with the same procedure on the tail of the list, until the tail becomes empty.

In Haskell, this is easily implemented like this:

map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

You’ll recognize in the Haskell definition that the empty list is mapped into empty list, and that x:xs means that we split the list into the head x and the tail xs. f x : map f xs means that we put f(x) (f applied on the head) in the result list and apply again the same snake procedure on the tail of the list, xs.

If you need any more clarifications, ask all the questions you need, I’m here to answer you!

P.S. Recursion is one of the most important processes in nature, for more informations about it you can read this article which shows the link between recursion and art:
Recursion in nature

Constantin Liculescu


Share Button