Списки

Неизменяемый односвязный список играет важную роль во многих функциональных языках, начиная с Лиспа. Списки состоят из так называемых CONS-ячеек (CONS cells), каждая из которых представляет собой пару (hd, tl), где hd – это некоторый элемент списка, а tl – либо указатель на оставшуюся часть списка, либо пустой список [] (пустой указатель). В Ficus все элементы списка обязаны иметь один и тот же тип (в отличие от динамически типизированных языков, таких как Лисп). Например, список чисел 1, 2 и 3 выглядит так:

---
config:
  layout: elk
  look: handDrawn
  theme: neutral
---
flowchart LR
    1 --> 2
    2 --> 3
    3 --> A@{ shape: f-circ, label: "Junction" }

То есть, связи идут только в одном направлении – от головы к хвосту, а хвостовой указатель последнего элемента – пустой указатель (null).

Такие списки удивительно мощный инструмент. В оригинальном Лисп единственным доступным типом данных был именно список, использовавшийся для представления всех видов данных, от иерархических структур до сложных программ на самом Лисп.

Списки в Ficus можно выразить двумя способами:

val list123 = [:: 1, 2, 3]
// или
val list123 = 1 :: 2 :: 3 :: []

// Операция :: правоассоциативна,
// так что второе выражение эквивалентно
val list123 = 1 :: (2 :: (3 :: []))

Оператор :: называется CONS (поэтому списки называются CONS-списками). Он берет скалярный головной элемент (элемент некоторого типа T), список tl (типа T list) и формирует новую ячейку (hd, tl), создавая таким образом новый список. Заметьте, что операция :: не изменяет исходный список tl – он остаётся неизменённым, потому что списки в Ficus неизменяемы. Из-за этого свойства список нельзя ни добавить в середину, ни удалить элемент посередине, ни присоединить элемент в конец. Хотя поначалу это кажется серьёзным ограничением, преимущество такой реализации заключается в сохранении предыдущих состояний списка:

val a = "a" :: []
val b = "b" :: a
val c = "c" :: b
println(b) // напечатает ["b", "a"]

Это свойство полезно для анализа кода, отладки и обеспечивает безопасность, поскольку операции со списками не имеют побочных эффектов (за исключением случая, когда элементы сами по себе изменяемы, например, массивы или ссылки). Списки относятся к функциональным структурам данных. Другой хороший пример неизменяемой структуры – красно-чёрное дерево поиска, которое мы рассмотрим позднее в разделе Варианты.

Ещё одно важное достоинство таких списков – практически любые возможные операции над ними можно выразить с использованием четырёх примитивных действий (при желании можно записать операцию в форме List.foo(l[, args]) вместо l.foo([args])):

Функция	Описание
`l.empty()`	Возвращает истину, если список пуст. Можно также сравнить список с пустым списком: `l == []` или `l != []`, что транслируется в высокоэффективный код.
`l.hd()`	Извлекает первый элемент первой CONS-ячейки, то есть получает голову списка. Если список пуст, возникает исключение `NullListError`.
`l.tl()`	Извлекает второй элемент первой CONS-ячейки, то есть хвост списка. Если список пуст, возникает исключение `NullListError`.
`x :: l`	создаёт новый список путём добавления нового головного элемента `x` к существующему списку `l`

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

val l0 = [:: 1, 2, 3]

// добавляет квадраты чисел в обратном порядке
val fold l = l0 for i <- 0:5 {i*i :: l}

// ошибка: все элементы должны быть одного типа
val err1 = 3.14 :: l

// получение третьего (счёт идёт с нуля) элемента списка
val x = l.tl().tl().tl().hd() // 0

// функция для получения n-го элемента списка
fun list_nth(l: 't list, n: int): 't =
    if n < 0 || l == [] {
        throw OutOfRangeError
    } else if n == 0 {
        l.hd()
    } else {
        list_nth(l.tl(), n-1)
    }

print(list_nth(l, 5)) // выводит 2
print(list_nth(l, 100)) // выбросит OutOfRangeError

Теперь покажем, как можно реализовать полезные функции обработки списков с использованием четырёх базовых операций. Эти функции обладают общими свойствами:

они универсальны и работают с любыми списками;
они не имеют побочных эффектов;
они написаны с использованием хвостовой рекурсии, следовательно, выполняются за линейное время O(N) и занимают постоянное пространство стека O(1);
большинство из них уже определены в стандартных модулях Builtins и List, но приведены здесь исключительно для иллюстрации и в образовательных целях.

Начнём с простой и широко применяемой функции обращения списка, которая также служит вспомогательной функцией для других операций:

// Реализация List.rev(l)
fun list_rev(l: 't list): 't list
{
    fun list_rev_(l: 't list, result: 't list): 't list =
        if l.empty() {result} else {list_rev_(l.tl(), l.hd() :: result)}
    list_rev_(l, [])
}

Эта реализация демонстрирует распространённый приём в функциональных программах – вместо цикла мы определяем внутреннюю рекурсивную функцию, принимающую текущее состояние ввода и промежуточный результат, а затем вызывает саму себя для продолжения итерации.

Рассмотрим следующую полезную функцию – подсчёт длины списка:

fun list_length_naive(l: 't list): int =
    if l.empty() {0} else {1 + list_length_naive(l.tl())}

Реализация проста, но у неё есть недостаток – здесь нет хвостовой рекурсии, так как фукнция производит дополнительные операции после рекурсивного вызова самой себя. Следовательно, её невозможно преобразовать в цикл, и она расходует память в стеке пропорционально длине списка O(N). Решить проблему можно, применив технику, использованную в list_rev:

// Реализация l.length()
fun list_length(l: 't list): int
{
    fun list_length_(l: 't list, len: int) =
        if l.empty() {len} else {list_length_(l.tl(), 1 + len)}

    list_length_(l, 0)
}

Следующая важная функция – объединение списков, реализованная в модуле Builtins как перегруженный оператор +:

fun list_concat(la: 't list, lb: 't list): 't list
{
    fun list_concat_(rev_la: 't list, result: 't list): 't list =
        if rev_la.empty() {result}
        else {list_concat_(rev_la.tl(), rev_la.hd() :: result)}

    list_concat_(list_rev(la), lb)
}

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

Все рассмотренные выше функции схожи по структуре: проверяют, пуст ли список (или его текущий хвост), если да – возвращают итоговый результат, иначе выполняют обработку головы списка и делают рекурсивный вызов для хвоста списка. Рассмотрим универсальный метод, называемый foldl, который реализует такую схему в более общей форме:

// Реализация List.foldl()
fun list_foldl(l: 't list, f: ('t, 'res)->'res, res0: 'res): 'res =
    if l.empty() {res0} else {list_foldl(l.tl(), f(l.hd(), res0), f)}

При помощи foldl легко переписать реализацию предыдущей функции list_length():

fun list_length2(l: 't list) =
    list_foldl(l, 0, fun (_: 't, len: int) {1 + len})

Обратите внимание, что для неиспользуемых параметров используется обозначение _.

Используя list_foldl()/List.foldl(), вам редко нужно будет писать собственные рекурсивные функции для обработки списков. Один из таких редких случаев – необходимость досрочного выхода из цикла обработки списка.

// Реализация List.find()
// Возвращает первый элемент, удовлетворяющий предикату.
// Если подходящего элемента нет, возвращает None.
fun list_find(l: 't list, pred: 't->bool): 't? =
    if l.empty() {None}
    else {
        val x = l.hd()
        if pred(x) {Some(x)}
        else {list_find(l.tl(), pred)}
    }

val l = [:: 1, 2, 3]
val first_even = list_find(fun (x) {x % 2 == 0}, l)
println(if first_even.issome() {
        string(first_even.value())
    } else {
        "нечётных элементов не найдено"
    }) // выводит "2"

Ещё одна частая операция – функциональное отображение элементов списка с последующим формированием нового списка результатов:

// Реализация List.map()
fun list_map(l: 'a list, f: 'a->'b): 'b list =
    list_foldl(list_rev(l),
                fun (x: 'a, res: 'b list) {f(x) :: res},
                ([] : 'b list))

// альтернатива, без хвостовой рекурсии,
// но не использующая обращение списка
fun list_map_alt(l: 'a list, f: 'a->'b): 'b list =
    if l == [] {[]} else {f(l.hd()) :: list_map_alt(l.tl(), f)}

val strs = [:: "1", "a", "2"]
// конвертирует строки в целые числа,
// некорректные строки заменяются на -1.
// Результат: [:: 1, -1, 2]
val nums = list_map(strs, fun (s: string) {s.to_int_or(-1)})

Отображение – это специальный случай свёртки, когда результатом является новый список. Аналогично можно переписать List.filter(), сохраняя только элементы, удовлетворяющие заданному условию.

Поскольку List.foldl() и List.map() столь распространены, в Ficus предусмотрены удобные сокращения с использованием оператора цикла и оператор свёртки, которые упрощают работу с этими функциями:

// Используем оператор свёртки вместо List.foldl()
fun list_length3(l: 't list): int = fold len=0 for x <- l { len + 1 }

// Используем генератор списков вместо List.map()
val nums = [:: for s <- strs {s.to_int_or(-1)}]

// Простая итерация по списку без построения результата
for s <- strs {
    println(s)
}

Хотя многие операции над списками легко реализуемы, стандартные модули (Builtins и List) предоставляют готовые решения для базовых функций. Вот полный перечень методов, доступных для списков:

Функция	Описание
`l.last()`	возвращает последний элемент списка Выбрасывает исключение `NullListError`, если список пуст
`l.nth(i)`	Возвращает i-й элемент списка
`l.length()`	Возвращает длину списка
`l.rev()`	Возвращает обращённый список (список в обратном порядке)
`l.app(f)`	применяет функцию `f` ко всем элементам списка. Функция должна возвращать `void`
`l.map(f)`	Создаёт новый список, применяя функцию `f` к каждому элементу исходного списка
`l.foldl(f, v0)`	Сворачивает список в значение, используя функцию `f` для преобразования элементов. Свертка начинается со значения `v0`
`l.array()`	Преобразует список в массив
`l.all(pred)`	Возвращает `true`, если предикат выполняется для всех элементов
`List.all2(la, lb, pred)`	Аналогична `List.all()`, но применяется к двум спискам
`l.exists(pred)`	Возвращает `true`, если предикат выполняется хотя бы для одного элемента
`l.mem(a)`	Возвращает `true`, если элемент `a` присутствует в списке
`l.find_opt(pred)`	Возвращает первый элемент, для которого выполняется предикат. Если подходящего элемента нет, возвращается `None`
`l.assoc_opt(a)`	Для списка пар `(a_i, b_i)` возвращает `Some(b_i)` для первой пары, где `a_i == a`. Если подходящей пары нет, возвращает `None`
`l.filter(pred)`	Сохраняет только те элементы в списке, для которых выполняется предикат.
`l.concat()`	Объединяет несколько списков. Существуют разные варианты этой функции. Для соединения двух списков достаточно записать `la + lb`
`List.zip(la, lb)`	возвращает список пар, состоящий из соответствий элементов списков `la` и `lb`
`l.unzip()`	Противоположна `List.zip()`, возвращает кортеж из двух списков `(la, lb)`
`l.sort(lt)`	Сортирует список с помощью функции сравнения `lt`

val a = [:: ("a", 5), ("c", 0), ("A", 1)]
// сортирует список пар по первому элементу;
// возвращает [:: ("A", 1), ("a", 5), ("c", 0)]
val b = a.sort(fun ((s1, n1): (string, int),
                (s2, n2): (string, int)) => s1 < s2)

Мы показали, как базовые операции над списками и некоторые другие алгоритмы можно выразительнее записывать с использованием механизма сопоставления с образцом.

Выбор между списком, вектором и массивом

** (Будет дополнено более подробным обсуждением) **

Для многомерных плотных данных (2D, 3D, …) предпочтительны массивы.
Используйте vector, если необходим неизменяемый список, кроме случаев, когда требуется сопоставление с образцом, тогда лучше применять список.
Несмотря на то, что доступ к элементам вектора выполняется за время O(1), произвольный доступ к вектору существенно медленнее, чем доступ к массиву. Последовательный доступ к элементам вектора близок по скорости к элементам массива.
Дополнительные затраты памяти заметны только для маленьких коллекций. Массивы требуют минимальных накладных расходов (0%), векторы – незначительных (несколько процентов), а списки заметно увеличивают потребление памяти и нагрузку на аллокатор. Поэтому для огромных массивов использование массивов или векторов предпочтительнее, поскольку использование списков создает значительную нагрузку на аллокатор и требует заметно больше памяти.