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

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

Для обозначения списков будем использовать нотацию, похожую на 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