Рассмотрим вариант реализации связных списков через замыкания.
Для обозначения списков будем использовать нотацию, похожую на Haskell:
В качестве языка реализации я выбрал JavaScript.
Для работы со связными списками необходимы следующие базовые примитивы:
Создание списка из двух элементов выглядит следующим образом:
Реализация функции
Функция
Реализация
Осталось реализовать пустой список (
Таким образом,
Несложная программа, иллюстрирующая конструирование и обход списка:
Для получившейся структуры данных можно реализовать функции высшего порядка, например,
Это позволит работать с нашими списками в функциональном стиле:
Другие ассоциированные функции (
При написании статьи ни один массив не пострадал.
Предвосхищая картинку про троллейбус из хлеба: это, безусловно, не прикладное решение. Более того, на работе за такой коммит могут легко и непринужденно оторвать руки. Что с этим знанием делать дальше — решать вам.
GitHub: github.com/mvasilkov/functional-js
Для обозначения списков будем использовать нотацию, похожую на 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