Functional linked lists

Consider the implementation of linked lists through closures .

To denote lists, we will use a notation similar to Haskell:, x:xswhere xis the beginning of the list ( head), and xsis continued ( tail).



I chose JavaScript as the implementation language.

Construct a list

To work with linked lists, the following basic primitives are required: nil- an empty list, prepend( cons) - an insert function at the top of the list, headand tail.

Creating a list of two items is as follows:

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

Function implementation prepend:

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

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

Implementation headand tailamounts to a call-list feature with the desired value select:

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 }

In this way head(nil) === tail(nil) === nil.

Usage example

A simple program illustrating the construction and traversal of a 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, higher-order functions can be implemented, for example map:

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

This will allow us 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, not a single array was damaged.

Anticipating the picture of a trolley from bread: this is certainly not an applied solution. Moreover, at work for such a commit, they can easily and unconstrainedly tear off their hands. What to do next with this knowledge is up to you.

Github: github.com/mvasilkov/functional-js