Functional Connected Lists

Consider the implementation of linked lists through closures .

To designate lists, we will use a notation similar to Haskell: x:xs , where x is the beginning of the list ( head ), xs is the continuation ( tail ).


')
As the implementation language, I chose JavaScript.

We construct a list

The following basic primitives are needed to work with linked lists: nil is an empty list, prepend ( cons ) is the insert function at the beginning of the list, head and tail .

Creating a list of two items is as follows:

 prepend('a', prepend('b', nil)) // 'a' -> 'b' -> nil 

The implementation of the prepend function:

 function prepend(x, xs) { return function (select) { return select(x, xs) } } 

The select function is needed to access free variables ( x:xs ).

The implementation of the head and tail is reduced to calling the list function with the desired select value:

 function select_head(x, xs) { return x } function select_tail(x, xs) { return xs } function head(a) { return a(select_head) } function tail(a) { return a(select_tail) } 

It remains to implement an empty list ( nil ):

 function nil() { return nil } 

Thus, head(nil) === tail(nil) === nil .

Usage example

A simple program illustrating the construction and traversal of the list:

 var a = prepend('a', prepend('b', nil)) // 'a' -> 'b' -> nil head(a) // => 'a' head(tail(a)) // => 'b' head(tail(tail(a))) // => nil while (a !== nil) { console.log(head(a)) a = tail(a) } 

Higher order functions

For the resulting data structure, you can implement higher-order functions, for example, map :

 function map(fn, a) { if (a === nil) return nil return prepend(fn(head(a)), map(fn, tail(a))) } 

This will allow you to work with our lists in a functional style:

 var a = prepend(1, prepend(2, prepend(3, nil))) // 1 -> 2 -> 3 -> nil function power_of_2(x) { return 1 << x } var b = map(power_of_2, a) // 2 -> 4 -> 8 -> nil 

Other associated functions ( filter , reduce ) are offered to the reader as homework.

Such things ™

When writing an article, no array was harmed.

Anticipating a picture of a trolley made of bread: this is definitely not an applied solution. Moreover, at work for such a commit can easily and naturally lift off their hands. What to do with this knowledge is up to you.

GitHub: github.com/mvasilkov/functional-js