Главная

Связные списки в функциональном стиле

2013-04-06 в 16:40, admin, рубрики: javascript, замыкания, ненормальное программирование, структуры данных, функциональное программирование, метки: замыкания, структуры данных, функциональное программирование

Рассмотрим вариант реализации связных списков через замыкания.

Для обозначения списков будем использовать нотацию, похожую на Haskell: x:xs, где x — начало списка (head), xs — продолжение (tail).

Связные списки в функциональном стиле

В качестве языка реализации я выбрал JavaScript.

Конструируем список

Для работы со связными списками необходимы следующие базовые примитивы: nil — пустой список, prepend (cons) — функция вставки в начало списка, head и tail.

Создание списка из двух элементов выглядит следующим образом:

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

Реализация функции prepend:

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

Функция select нужна для доступа к свободным переменным (x:xs).

Реализация head и tail сводится к вызову функции-списка с нужным значением 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) }

Осталось реализовать пустой список (nil):

function nil() { return nil }

Таким образом, head(nil) === tail(nil) === nil.

Пример использования

Несложная программа, иллюстрирующая конструирование и обход списка:

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)
}

Функции высшего порядка

Для получившейся структуры данных можно реализовать функции высшего порядка, например, map:

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

Это позволит работать с нашими списками в функциональном стиле:

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

Другие ассоциированные функции (filter, reduce) предлагаются читателю в качестве домашнего задания.

Связные списки в функциональном стиле

Такие дела™

При написании статьи ни один массив не пострадал.

Предвосхищая картинку про троллейбус из хлеба: это, безусловно, не прикладное решение. Более того, на работе за такой коммит могут легко и непринужденно оторвать руки. Что с этим знанием делать дальше — решать вам.

GitHub: github.com/mvasilkov/functional-js

Автор: printf

Источник