Back

On linked lists, mapping, folding, and recursion

|

Let's talk about lists, or more specifically, linked lists.

A linked list is a very simple data structure that represents ordered sequences.

The beauty оf linked lists is the simplicity of implementing them and the beautiful recursive functions we can write to handle them.

The concept is really straight forward:
A list is a node with value, and a reference to the next node in the list.

The 1,2,3,4 list could be viewed like this:

{
    value: 1,
    next: {
        value: 2,
        next: {
            value: 3
            next: {
                value: 4
                next: null
            } 
        }
    }
}

Or even simpler, as a function that returns an object:

var node =  
    function (value, next) {
        return {
            value: value,
            next: next
        }
    }

With this new function the list will look like this:

node(1, node(2, node( 3, node(4))));  

It might look confusing, but that's a list right there.

You can think of the node function as a function that adds an item to a list.
If that's the case, the node(4) call at the end of the chain is adding 4 to null which we use to represent an empty list.

If we want to be a bit more descriptive we could do some renaming:
We'll set a constant EMPTY_LIST to the value of null and add the alias 'add' to the 'node' function.

var EMPTY_LIST = null;  
var add = node;  

Now our list looks a bit clearer:

var myList = add(1,  
             add(2,
             add(3,
             add(4, EMPTY_LIST))))

myList.value // 1;  
myList.next.value // 2;  
myList.next.next.value // 3;  

But it doesn't look like the best way to get items out of our lists at the moment, so let's create some helpers for that.

We'll start with 2 very basic functions:

  • One function that will return the value of the first item in the list, we'll call it head.

  • The second function will be named tail and will return the list without the head.

       [1]          [2][3][4]
        ^            ^^^^^^^
       Head           Tail
    

the implementation is really straight forward:

var head =  
    function (list) { return list.value; }

var tail =  
    function (list) { return list.next; }

head(myList); //1  
head(tail(myList)); //2  
head(tail(tail(myList))); //3  

"Okej" you must think to yourself, That's cool and all but that isn't such a beautiful way to get an item from a list in a specific position.

And you'll be right! so let's add another function, nth.
Nth will look like this: nth(list, position)
and will return us the value of the node in a given position in the list.

var nth =  
    function (list, position) {

        if (position == 1) return head(list);

        return nth( tail(list), position - 1);
    }

nth(myList, 1) //1  
nth(myList, 3) // 3  

Much better! and such an elegant solution!
If you are not familiar with recursive functions you might be a bit confused right now, so I'll explain
what's going on here a bit better.

When thinking in the recursive mind set you need to think about what IS something, and not HOW to do it.

  • So what IS the nth element of a list?

  • Well, if the position we are looking for is the first one then it's just the head of list.

  • And if it isn't? Then it's nth of the tail of the list when the position we are looking for is smaller by 1.

Still confused? let's try it again.

We have a list: 1,2,3,4

We want to get an element out of this list based on the position of the element in the list.

  • What if we want the first element in the list?

  • Well, if the position we are looking for is the first one then it's just the head of list: head(list) // 1

  • what if we want the third element in this list?

  • well that's the same as the second element of the tail of the list!

  • ok, so what is the second element of 2,3,4? well that's the same as the first element of the tail of the list!

  • ok, so what is the first element of 3,4? Well, if the position we are looking for is the first one then it's just the head of list:
    head(list) // 3

Isn't it just beautiful?
Don't you feel like having a tattoo of this function in Japanese?

n番目=  
    機能(リスト、位置){

        もし(ポジション==1)リターンヘッド(リスト); 

        n番目のリターン()尾(リストを、位置 - 1);
    }

beautiful.

Functions all the way down

"But wait!"
You say.
"it's nice that I can retrieve items from the list, but maybe I actually want to process them too. You know, iterate over them and such."

Write more recursive functions then!

Let's say you want get the length of a list, you can introduce a new function called "length":

var length =  
    function (list) {

    }

Think recursively

  • What IS the length of a list?

  • Well, if the list has no elements, it's zero.

  • True! but what if it does?

  • Then the length is 1 + the length of the tail of the list.

  • What IS the length of a the tail of the list?

  • Well, if the list has no elements, it's zero.

  • True! but what if it does?

You can see the pattern.
Eventually, you will reach an EMPTY_LIST at the end of your list, then you can break from your recursive function.

var length =  
    /// What IS the length of a list?
    function (list) {
        /// Well, if the list has no elements, it's zero.
        if (list == EMPTY_LIST) return 0;
        /// True! but what if it does? 
        /// Then the length is 1 + the length of the tail of the list.
        return 1 + length( tail(list) )
    }

length(myList)//4  

Bang. Beautiful.

"Alright, alright!"
You must think to yourself again.
"Recursion is cool, but what if I actually want to iterate the nodes and modify them, I'm not going to write a dedicate function for every iteration i'm doing!"

Well you're right again.
Iteration is important, and we should write us some helpers to make it an easy task.

In the functional paradigm, iteration over lists is usually done with one of this 3 functions:
map, filter, fold.

So let's implement them all and see where it takes us.

map

Let's start with map:
The map function accepts two parameters, a list to iterate on, and a function to apply on every iteration.
It then iterates over each item in a list, does something to it, and put it back in that list.

With procedural code it will look like this:

var doStuffToArray =  
    function (toParse) {
        var parsed = [];

        for (var item in toParse) {
            parsed.push( parseThisItem (item) );
        }

        return parsed;
    }

And with functional code it might look like this:

var doStuffToArray =  
    function (toParse) {
        return map(toParse, parseThisItem);
    }

Now this one might be harder to understand than the last ones, as it is a bit more complex.

But the concept is the same.

  • What IS a mapped list?

  • Well, if it's an empty list, then it's an empty list as well.

  • And if it isn't?

  • Well in that case it's the head of the list after being applied the mapper added to the map of the tail of the list.

let's break it down

We have a list: 4,3,2

we want to iterate over it and apply the pow function on each element.

so what is map(myList, pow)?

  • Well, if it's an empty list, then it's an empty list as well.

  • It isn't.

  • So it's the head of the list, 4, with the pow function applied on it, 16, added to the tail of the list after being mapped.

  • Ok, so what IS the tail of the list after being mapped?

  • Well, if it's an empty list, then it's an empty list as well.

  • Well the list isn't empty,

  • So it's the head of the list, 3, with the pow function applied on it, 9, added to the tail of the list after being mapped.

  • Ok, so what IS the tail of the list after being mapped?

  • Well, if it's an empty list, then it's an empty list as well.

  • Well the list isn't empty,

  • So it's the head of the list, 2, with the pow function applied on it, 4, added to the tail of the list with after being mapped.

  • Ok, so what IS the tail of the list after being mapped?

  • Well, the tail of the list is an empty list, so it is an empty list as well.

so after this long recursive chain, we can say that this what happened:

add( pow(4),  
    add( pow(3) ), 
        add( pow(2), EMPTY_LIST); 

We basically built a new list, where the values in that list are our original values with pow applied on them.
Isn't that cool?
I think it's cool.

Now let's implement it.

var myList = add(4,  
                add(3,
                    add(2, EMPTY_LIST)))
var map =  
    /// What IS a mapped list?
    function (list, mapper) {
        /// well, if it's an empty list, then it's an empty list as well.
        if (list == EMPTY_LIST) return EMPTY_LIST;
        /// and if it isn't? 
        /// well it's the head of the list after being applied the mapper added to the map of the tail of the list.
        return add( mapper( head( list ) ), 
                    map( tail( list ), mapper) )
    }

var pow = function (n) { return n * n}

powedList = map(myList, pow);  
nth(powedList, 1) // 16  
nth(powedList, 2) // 9  
nth(powedList, 3) // 4  

Nice.

filter

The next function used to iterate over lists is "filter".

Filter is a function that accepts a list and another function, it then iterates over the list, and applies the function on each item, if the result is FALSE it will filter out the item from the list, and if it's true, it will keep it there.

With procedural code you could achieve it using code that looks like this:

var filterOddNumbers =  
    function (list) {
        var notOdd = [];
        for (item in list) {
            if (isEven(item)) notOdd.push(item);
        }

        return notOdd;
    }

the functional equivalent will look like this:

var filterOddNumbers =  
    function (list) {
        return filter(list, isOdd);
    }

Let's go over it again!

so..

  • What IS a filtered list?

  • Well as always, if the list is empty, the filtered version is also an empty list.

  • And if it isn't empty?

  • Well, depends. does applying the predicate on the head of the list returns true?

  • If so, the filtered list is the head of the list added to the filtered tail.

  • If it isn't, the filtered list is the just the filtered tail.

  • Yeah but what is the filtered tail?

  • Well as always, if the list is empty, the filtered version is also an empty list.

  • And if it isn't empty?

  • Well, depends. does applying the predicate on the head of the list returns true?

I think you can see where this is going.

So now when we know the expected functionality, let's implement it!

var filter =  
    function (list, pred) {
        /// if the list is empty, the filtered version is also an empty list.       
        if (list == EMPTY_LIST) return EMPTY_LIST;

        var lhead = head(list),
            ltail = tail(list);
        /// And if it isn't empty?
        /// Well, depends. does applying the predicate on the head of the list returns true?
        if ( pred(lhead) )  {
            /// if so, the filtered list is the head of the list added to the filtered tail,
            return add(lhead, filter( ltail, pred));
        } else {
            // if it isn't, the filtered list is the just the filtered tail.
            return filter(ltail, pred);
        }
    }

var isEven =  
    function (n) { return n % 2 == 0}

var myEvenList = filter(myList, isEven);

var print = function (n) {  
    console.log(n);
    return n
};

map(myEvenList, print) // prints: 4 2  

Fold

The next helper I would like to discuss is "fold" (also known as "reduce").
Many times you would want to iterate over a list and have some variable that you will change based on the items in list.
for example, adding all of the numbers in a list.

In procedural code, you will do it like this:

var adder = function (n,m) { reutrn n + m }

var addAllItemsInList =  
    function (list) {
        var result = 0;

        for (item in list) {
            result  = adder(result, item);
        }

        return result;
     }

Using "fold", it will look like this:

var addAllItemsInList =  
    function (list) {
        return fold(list, adder, 0);
    }

So fold accepts three parameters:

  • a list

  • a function

  • an inital value.

It will then iterate over the list, and will call the function with 2 values:
the item currently iterated and a variable which holds the value of whatever was returned by this function the last iteration,

This special variable passed to the function with every iteration is called "accumulator".

Piece of cake right! if you got the last 2 this one is a no brainer.

  • if the list is empty, the result of the fold is the accumulator.

  • if it isn't? the result is the fold of the tail, with the same folder, but this time with the accumulator being the result of applying the head and the accumulator on the folder function.

Japanese tattoos everywhere.

var fold =  
    function (list, folder, accumulator) {
        /// if the list is empty, the result of the fold is the accumulator.
        if (list == EMPTY_LIST) return accumulator;
        /// if it isn't? the result is the fold of the tail, with the same folder, 
        /// but this time with the accumulator being the result of applying the head and the accumulator on the folder function.
        return fold(tail(list), folder, folder(accumulator, head(list)))
    }

Bam.

let's give it a test run:

var list = add(1, add(2, add(3, add(4, EMPTY_LIST))));  
var adder = function (a,b) { return a + b};  
var sum = fold(list, adder, 0);  
console.log(sum) // 10  

Fold is so awesome you can use it to implement even more functions!

More functions, more recursion.

Let's try to use fold to introduce a new function: 'has'.
Has will accept a list and a value and return true if the value is in the list, or false if it isn't.

var has =  
    function (list, needle) {
        return fold(list, function (acc, val) {
                return acc || (val == needle);
        }, false)
    }
has(list, 1) //true  
has(list, 5) //true  

Let's try 'count'!
A function that will count how many times an item is in a list.

var list = add(1, add(1, add(2, add(2, add(1, EMPTY_LIST)))));

var count =  
    function (list, needle) {
        return fold(list, function (count, val) {
            return needle == val? count + 1 : count
        }, 0)
    }

count(list, 1) //3  
count(list, 2) //2  
count(list, 3) //0

Wrap it up

To wrap it up - using very simple and small functions we are the able to implement most of the list related functions in standard libraries.