Программирование на Athanor - 5 (простейшие списки)

Базовые операции над списками

Рассмотренные нами скаляры – это простейшие (тривиальные) типы данные. А основная НЕтривиальная структура данных в языке – это список.

Любой список может содержать произвольное (ненулевое) число элементов. Списки гетерогенны, они могут содержать элементы разных типов. (Или же элемент списка может быть пустым, т.е. иметь значение ().) Элементом списка может быть и другой список – и вообще, списки могут быть вложенными на произвольную глубину. Однако, тут есть свои тонкости, так что мы пока отложим знакомство с иерархическими списками, и ограничимся лишь "плоскими" (то есть, состоящими исключительно из скалярных элементов). Все списки мутабельны: содержимое любого созданного списка можно изменять, добавляя, удаляя или изменяя его элементы. Простейший нетривиальный список – это список, состоящий из двух элементов. (Собственно говоря, все рассмотренные выше скалярные бинарные операции имели один операнд: двухэлементный список.)

Поскольку списки играют настолько важную роль, в языке предусмотрено довольно много способов записи для них. Простейший (и самый употребительный) таков:

• (Elem1, Elem2, ... ElemN)

Здесь Elem1 ... ElemN – это последовательное перечисление всех элементов списка (разделённых запятыми). Например, (1, 2, 3, 4, 5) – это просто список из первых пяти натуральных чисел. Однако, когда (как в данном случае) элементами списка являются скалярные литералы, допускается альтернативная (и более компактная) запись для списка:

• [Elem1 Elem2 ... ElemN]

Здесь все элементы имеют тривиальный синтаксис, и явные разделители между ними не нужны – их роль играют пробелы (или любые пробельные символы). Например, [1 2 3 4 5] – это всё тот же список, но в более компактной форме. (Но, на самом деле, элементом списка «в квадратных скобках» может быть не только литерал, но и произвольное синтаксически замкнутое выражение, включая другой список. Но это сейчас для нас не принципиально.)

Что можно делать со списками? Полный набор операций, определенный для списков, очень и очень обширен – но пока ограничимся наиболее употребительными. Как и для скалярных операций, многие из них имеют и операторную, и функциональную запись (функторы, связанные со списками, обычно начинаются с префикса "l_").

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

Длина списка – это просто количество элементов в нём. Для большинства списковых операций действует ещё одно правило: неявная векторизация. Там, где требуется списковый операнд, допускается и скаляр, который рассматривается как список из одного элемента. (Что не означает, что скаляры являются списками! Это означает всего лишь то, что многие списковые операции рассматривают их как некую "вырожденную" форму списков.) Поэтому, применение этой операции к любому скаляру – тоже допустимо (и оно всегда возвращает 1). Для пустого значения () – функтор l_len возвращает 0 (и это единственное значение в языке, для которого данная операция может вернуть нуль!)

Также полезна операция для сцепления списков:

Эта операция возвращает список, в котором за элементами списка L идут элементы списка M. Очевидно, что справедливо тождество #(L [+] M) == (#L + #M). Любой из операндов может быть скаляром (даже оба) – в этом случае, скаляр просто присоединяется к списку в начале и/или конце.

Есть операция для создания списка из повторяющегося элемента (или нескольких элементов):

Репликация возвращает список, представляющий собой повторение элементов списка L (n раз подряд). Если L является скаляром, то результатом является список из n копий значения L. Если n == 1, то просто возвращается L. Если n <= 0 – результатом l_rep будет (). Для этой операции тоже имеется своё тождество: #(L [*] n) == (#L * n). Заметим, что в функциональной форме порядок операндов обратный (n идёт первым, это не случайно).

Реверсия имеет только один операнд L, и возвращает список из всех элементов L в обратном порядке. Если L является скаляром, то результатом просто является L (а если L пусто – то значение () и будет результатом). Для этой операции есть своё тождество: #([~] L) == #L.

Результатом этой операции является точная копия списка L. Можно задаться вопросом: а зачем копировать список? Дело в том, что в большинстве случае язык избегает автоматического копирования списков, ради эффективности. (При присваивании, например, не создаётся никакого нового списка – просто добавляется ещё одна ссылка на существующий.) Однако, при этом списки мутабельны – а это означает, что список можно изменить (когда мы имеем дело с несколькими копиями одного списка в разных местах, это может вызвать проблемы). Вот почему полезна операция для явного создания копии списка (которую можно бесцеремонно изменять, не опасаясь так "испортить" оригинал). Конечно, если изменять копию списка не планируется, то операция l_copy обычно не требуется. Заметим, что копирование списка не ограничивается одним уровнем: когда его элементы сами являются подсписками, они тоже копируются. Вот когда элементы являются другими (не списковыми) структурами данных, их автоматического копирования уже не происходит (однако, тут мы уже сильно забегаем вперёд).

Однако, если списки мутабельны, то как их можно изменять? Проще всего – поэлементно:

Функтор l_item является аксессором, то есть операцией доступа: он предоставляет доступ к элементу списка L с индексом n. Причём, результат мутабелен, то есть этот элемент можно изменить. Надо чётко различать аксессоры и мутаторы: первые предоставляют возможность изменения внутри какой-нибудь структуры данных, а вторые уже изменение производят. Например, если написать L[5] = 100 (или set (l_item (5, L), 100) в чисто функциональной форме), то элементу списка L с индексом 5 присваивается значение 100. (Заметим, что в функциональной записи индекс элемента идёт самым первым – это, опять-таки, не случайно.)

Как и строки, элементы списка индексируются с нуля, поэтому последний элемент списка L имеет индекс #L - 1. Если значение индекса больше или равно #L – то результатом будет (). Этот результат уже не мутабелен: присваивать значения несуществующим элементам списка нельзя! В языке не бывает автоматического "расширения" списка (как, например, в Perl): если присвоить что-то элементу со слишком большим индексом, то интерпретатор сообщает об ошибке, а присваиваемое значение теряется. (Размер списка можно явно изменить функтором l_resize - но его мы рассмотрим позже.)

Наконец, для списков (как и для большинства сложных типов данных) определены собственные итераторы:

Обе эти операции выполняют (как правило, многократно) свой операнд Loop, перед каждой итерацией присваивая переменной V значение очередного элемента списка List. Различаются они исключительно порядком прохода по списку: для l_loop элементы перебираются в прямом порядке, для l_loop_r – в обратном. В обеих формах операнд Loop выполняется/вычисляется #List раз. Как и прочие итераторы, эта операция возвращает значение: последний результат Loop. Если вместо List оказался скаляр, то Loop (по общей логике векторизации) выполняется ровно один раз для значения V равного List; если List равно () – Loop не выполняется ни разу, а значением тоже является (). Обе операции эффективнее, чем использовать (например) for_inc/for_dec (на каждой итерации обращаясь к соответствующему элементу списка).

С ещё одной (очень тривиальной) формой задания списков (диапазоном) мы уже сталкивались. Диапазон From..To – это просто специальная форма записи для списка из двух элементов (From, To). Например, вызов for_inc (I, 10..20, Loop) – эквивалент для for_inc (I, (10, 20), Loop). Однако, первая форма компактнее (и нагляднее). С другой стороны, операцию диапазона тоже можно использовать как вполне универсальный конструктор списков (если использовать скобки – даже произвольной длины), но это не рекомендуется, чтобы не вносить лишнюю путаницу. Лучше ограничить её использование там, где операндом является диапазон чисел (в s_slice, for_inc/for_dec и нескольких других функторах, которые мы рассмотрим позже).

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

Применение скалярного бинарного функтора к списку - возвращает список, в котором два первых элемента заменены на результат применения к ним этого функтора (остальные оставлены без изменения). Формально, binary_op (E0, E1, E2, ... En) – эквивалентно (binary_op (E0, E1), E2 ... En). Например: add (10, 20, 30, 40) – возвращает (30, 30, 40).

Применение скалярного унарного функтора к списку - возвращает список, в котором первый элемент заменен на результат применения к нему этого функтора (остальные оставлены без изменения). Более формально, unary_op (E0, E1, E2, ... En) – эквивалентно (unary_op (E0), E1, E2 ... En). Например, neg (10, 20, 30, 40) – возвращает (-10, 20, 30, 40).

Как видим, применение унарной скалярной операции к списку – возвращает список той же длины, а бинарной – возвращает список, который на один элемент короче. Применение той же операции несколько раз – позволяет свернуть (или редуцировать) список до скалярного результата. Например, если список L равен (10, 20, 30, 40), то add(add(add(L))) имеет результатом 100 (арифметическую сумму всех элементов в L). Хотя это полезно, но вручную повторять обращение к add необходимое количество раз не очень удобно (и представьте себе, что в списке L несколько сотен элементов!)

К счастью, в языке есть специальная операция, которая всё это делает автоматически. Выполнение reduce (binary_op (List)) – имеет результатом (#List - 1) последовательных применений binary_op: сперва к первой паре элементов списка List, потом к предыдущему результату и следующему элементу списка и так далее, пока список не "кончится" и не "свернётся" в скаляр. Эта операция называется свёрткой, или редукцией. Например, для того же списка L: reduce(add(L)) сразу вернёт 100. (Под свёрткой мы имеем в виду исключительно результат: эта операция не мутатор, и с исходным списком ничего не произойдёт!) Вот основные бинарные операции, для которых полезна редукция:

• reduce (add (List)) – сумма всех элементов List
• reduce (mul (List)) – произведение всех элементов List
• reduce (max (List)) – наибольший из всех элементов List
• reduce (min (List)) – наименьший из всех элементов List
• reduce (s_cat (List)) – строковая конкатенация всех элементов List
• reduce (s_max (List)) – (словарно) последний из всех элементов List
• reduce (s_min (List)) – (словарно) первый из всех элементов List

И в заключение, осталось рассмотреть лишь предикат, проверяющий свой операнд на список:

Результатом является 1, если V – список, и 0 в противном случае. (Понятно, что в этой операции никакой векторизации операнда не происходит.)

Разумеется, это ещё далеко не все операции, которые определены для списков! Но другие требуют более углублённого знакомства с языком, и их мы пока что отложим.