Руководство для учащихся по функциональному программированию №1: Реализация списков в JavaScript

Хотя эта статья была написана первой, я предлагаю вам прочитать приквел, который я прочитал в качестве фона. Оставив ссылку ниже.

Есть много статей, посвященных функциональному программированию. Они упоминают неизменность, первоклассные функции, чистоту, рекурсию и многие другие понятия, обычно с небольшими примерами каждого из них. В этой серии я хочу попробовать другой путь. Мы будем реализовывать функциональные структуры данных, используя минимальное подмножество Javascript. Никаких циклов, никаких изменяемых переменных, никаких встроенных функций, кроме примитивных типов.

Первой из этих структур данных является список. Список — это очень простая структура данных, ниже приведено простое определение типа списка в машинописном тексте.

type List = { variant: "nil" } | { variant: "cons", elem: any, rest: List }

Здесь у нас есть либо вариант «nil» без элементов, либо вариант «cons» с элементом en, а также остальная часть списка. Прежде чем углубляться в детали реализации, давайте представим, как будет выглядеть такой список.

Ниже приведены те же определения в коде Javascript.

const emptyList = { variant: "nil" }; \\ []
const singleElemList = { variant: "cons", elem: 2, rest: emptyList } \\ [1]
const twoElemList = {
  { variant: "cons", elem: 1,
  rest: { variant: "cons", elem: 2, 
  rest: emptyList }
} // [1, 2]

Мы начинаем с первого элемента с узлом variant: "cons", конец мы обозначаем узлом variant: "nil".

Здесь у нас будет два конструктора, по одному на каждый вариант.

const mkEmpty = () => (
    {
        variant: "nil"
    }
)

const mkList = (elem, rest) => (
    {
        variant: "cons",
        elem: elem,
        rest: rest
    }
)

Если мы хотим составить список только из одного элемента, мы могли бы легко составить их.

const mkListFromElem = (elem) => (
    mkList(elem, mkEmpty())
)

Реализация средств доступа довольно проста.

const isEmpty = (list) => (
    list.variant === "nil"
)


// Below, we introduce the list notation. ":" is the prepending operation.
// (elem : rest) -> elem
// Get first element
const head = (list) => (
    list.elem
)

// Get the rest of the list
// (elem : rest) -> rest
const tail = (list) => (
    list.rest
)

Поскольку теперь у нас есть основные строительные блоки, мы можем приступить к определению более сложных функций. Во-первых, это функция длины.

// length(elem:rest) = 1 + length(rest)
const length = (list) => (
    isEmpty(list) ? 0 : 1 + length(tail(list))
)

Определение идет, если у вас есть пустой список, этот список имеет 0 длину. Для любого другого списка вы можете добавить один к длине остального списка и вернуть его.

length(list) = length([list.head]) + length([list.rest]) — это отношение, которое мы используем для этой функции.

Хотя мы могли бы продолжать реализовывать функции специальным образом, теперь я познакомлю вас с картой, фильтрацией и уменьшением функций высшего порядка. Затем мы будем использовать эти функции в качестве строительных блоков более сложных функций.

const map = (list, f) => (
    isEmpty(list) ? mkEmpty() : mkList(f(head(list)), map(tail(list), f))
)

Функция карты применяет функцию f ко всем элементам списка. Вы можете видеть, что мы эффективно воссоздаем список, вычисляя f на head(list) и передавая его в map(tail(list), f).

const filter = (list, p) => (
    isEmpty(list) ?
        mkEmpty()
        : f(head(list)) ?
            mkList(head(list), filter(tail(list), p))
            : filter(tail(list), p)
)

Фильтр принимает список и предикат p, предикат — это тип функции, которая возвращает логическое значение. Фильтры создают список с элементами, передающими предикат.

const reduce = (list, f, acc) => (
    isEmpty(list) ? acc : reduce(tail(list), f, f(acc, head(list)))
)

Уменьшение — это последний из наших строительных блоков. Мы используем reduce для применения функций к списку путем распространения результата. Я обычно нахожу, что сокращение вызывает наибольшее замешательство среди этих трех, поэтому давайте воспользуемся сокращением для некоторых функций, чтобы обеспечить более полное понимание.

// Instead of recursively calling tail ourselves, we call reduce
// with the initial value of 0, incremented for every node.
const lenReduce = (list, f) => (
    reduce(list, (acc, elem) => acc + 1, 0)
)

// Reverse initiates an empty list. At every point, we take the
// head, prepend it to the accumulator.
const reverse = (list) => (
    reduce(list, (acc, elem) => mkList(elem, acc), mkEmpty())
)

Другим важным строительным блоком является concat, который позволяет нам объединить два списка.

// We will use ++ for concat notation.
// concat(l1, l2) = l1 ++ l2

// If the first list is empty, we can just return the second list.
// Otherwise, we concatenate the rest of the list with and prepend
// the first element of the first list.
const concat = (list1, list2) => (
    isEmpty(list1) ? 
        list2 
        : mkList(head(list1), concat(tail(list1), list2))
)

Поскольку у нас есть concat, теперь мы можем определить начало и добавление.

// prepend(list, elem) = (elem : list)
const prepend = (list, elem) => (
    mkList(elem, list)
)

// append(list, elem) = list ++ [elem]
const append = (list, elem) => (
    concat(list, mkListFromElem(elem))
)

Как видите, prepend — это то же самое, что и mkList, а append эквивалентно созданию списка из одного элемента и объединению его в конец.

Последняя функция, которую мы реализуем, — это функция индексации. Здесь мы передаем параметр индекса n и уменьшаем его по мере перемещения по списку.

// nth((elem:rest), n) = nth(rest, n - 1)
const nth = (list, n) => (
    n === 0 ? head(list) : nth(tail(list), n - 1)
)

Ниже приведен репозиторий Github для функций, представленных в этой статье.