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

    Also popular now: