Мы продолжим разговор о списках, начатый ещё в пятой статье. Там мы рассматривали списки исключительно как линейные структуры данных (вроде одномерных массивов или векторов). Действительно, списки очень часто используются в таком качестве, и многие списковые операции рассматривают их именно так. Тем не менее, на техническом уровне список – это совсем не вектор, а бинарное дерево. Которое состоит из элементарных списковых ячеек, каждая из которых имеет только два элемента, по традиции называемых его "головой" (head) и его "хвостом" (tail). Однако, каждый из этих элементов – тоже может быть списком! Именно тот факт, что "хвостом" списка тоже может быть список - даёт возможность создавать списки из произвольного количества элементов (что мы уже и делали раньше). Вместе с тем, "голова" любого элемента списка тоже может быть списком – и это даёт возможность создавать вложенные списки неограниченной глубины. (Правда, ещё раз заметим, что и "длина", и "глубина" здесь – понятия довольно условные: они определяются тем, как на список смотрим мы).
Рассмотрим, например, "линейный" список L = (1, 2, 3, 4, 5). Фактически, он состоит из двух элементов: головы (скаляра 1) и хвоста (списка (2, 3, 4, 5)). Хвост в свою очередь можно разложить – и так далее, вплоть до самой последней ячейки списка (головой и хвостом которого являются скаляры 4 и 5). Таким образом, даже вполне линейный список – по своей природе, рекурсивная структура данных. Это означает, что список L можно записать и так: (1, (2, (3, (4, 5)))). Или даже так: [1 [2 [3 [4 5]]]]. Обе эти записи – дают совершенно тот же результат. Просто, скобки (круглые или квадратные) вокруг самого последнего элемента списка обычно можно опустить (они и так предполагаются).
Но можно и создавать список с помощью явной операции-конструктора со следующим синтаксисом:
Бинарная операция "::" – создаёт новую списковую ячейку (из головного элемента Head и хвостового элемента Tail). Она по функции аналогична примитиву cons в LISP. С помощью этой операции можно сформировать любой, даже самый сложный список. Например, всё тот же список L можно записать и таким образом:
Но в данном случае, всё записывается и короче! Операция "::" является право-ассоциативной (т.е., группирует свои операнды справа налево) – поэтому, все скобки здесь можно просто опустить, и результат будет тот же:
Однако, со списками связан довольно нетривиальный момент. Когда мы включаем список как последний элемент в другой список – он становится не отдельным его элементом, а фактически его продолжением! Но что, если последним элементом списка – тоже необходимо сделать список (и именно в качестве отдельного элемента)? Для этого в языке предусмотрена специальная форма списков: открытые списки. (Все списки, рассмотренные нами ранее, были "закрытыми"). "Открытые" списки отличаются от "закрытых" одним – структурой своей самой последней ячейки. В "закрытом" списке – она содержит предпоследний элемент в качестве "головного", и последний – в качестве "хвостового". В "открытом" списке – в последней ячейке головным является последний элемент, а хвостовой просто отсутствует, т.е., им является (). Фактически, открытый список – это закрытый список, в конец которого добавлен ещё и пустой элемент (). Однако (по соглашению!) большая часть операций над списками – игнорирует этот (), так как не считает его за "полноценный" элемент! Операция l_len не включает его в свой подсчёт элементов, итераторы l_loop и l_loop_r – не вызываются для него и т.п. И вообще: большая часть "линейных" списковых операций для открытых списков ведёт себя так, будто этого "последнего" элемента просто не существует.
Открытые списки тоже можно создавать многими способами! Для самого распространённого синтаксиса – в круглых скобках, и через запятую – после последнего элемента достаточно просто поставить дополнительную запятую:
Для списка в квадратных скобках есть свой специальный синтаксис: т.к. запятых в них нет, то надо или поставить в качестве последнего завершающего элемента () – или просто перед последней закрывающей скобкой должно стоять двоеточие ":"
Наконец, когда мы используем явные списковые конструкторы, никакого специального синтаксиса не предусмотрено, но можно явно задать () как последний элемент:
Во всех предыдущих примерах – мы определили открытый список из целых чисел с 1 по 5. Заметим, что он очень похож на закрытый список из всё тех же элементов – но, строго говоря, совсем ему совсем не идентичен! Многие операции (например, операции сравнения на идентичность, с которыми познакомимся позднее) – будут считать эти два списка различными. Открытые списки предпочтительнее закрытых в случаях, когда последним элементом должен быть список – и когда желательно иметь удобную возможность добавлять элементы в самый конец списка (с закрытыми списками это тоже можно, но несколько сложнее). Если списковую структуру должны иметь любые элементы, кроме последнего – делать список открытым, как правило, вообще нет необходимости.
У бинарной операции "::" есть ещё один неочевидный аспект. Она имеет более высокий синтаксический приоритет, чем любая операция вызова функтора, типа func(arguments). На практике, это означает, что запись f(a):: g(b) интерпретируется совсем не так, как вы (возможно) ожидали: не как (f(a), g(b)) – а как f(a, g(b))! Другими словами, операция "::" сразу после вызова функтора – "затягивает" свой второй аргумент внутрь скобок (добавляя его "хвостом" к уже заданному списку аргументов для f). Если же это не то, что вам требуется – явно поставьте круглые скобки вокруг первого операнда: (f(a)):: g(b). И вот это – действительно, просто синоним для (f(a), g(b)).
Такая особенность синтаксиса может показаться неожиданной – но, на самом деле, она довольно практична! В языке очень часто встречаются конструкции с вложением вызовов функторов в другие вызовы (причём, вложенность может быть не двухуровневой, а существенно более глубокой). С некоторыми из них мы уже сталкивались – например, с условиями и циклами. Использование операции "::" очень часто позволяет записать многие из них более изящно, более наглядно, и с меньшим количеством запутывающих круглых скобок. Как в следующих примерах:
| if (Cond):: (Then):: (Else) | if (Cond, (Then), (Else)) |
| unless (Cond):: (Else):: (Then) | unless (Cond, (Else), (Then)) |
| while (Cond):: (Loop) | while (Cond, (Loop)) |
| until (Cond):: (Loop) | until (Cond, (Loop)) |
| times (Count):: (Loop) | times (Count, (Loop)) |
Можно привести больше примеров, но идея, думаю, понятна. Именно такую запись мы будем довольно часто применять и в дальнейших примерах.
Мы уже знаем, как изменять список поэлементно – посмотрим теперь, как можно вставлять и удалять его элементы. Ключевую роль тут играют следующие операции:
|
l_head (List)
|
Доступ к "голове" списка List
|
|
l_tail (List)
|
Доступ к "хвосту" списка List
|
Функционально эти операции аналогичны примитивам car и cdr в LISP. Для каждой списковой ячейки, они обеспечивают прямой доступ к её "головному" и "хвостовому" элементам. Но ещё существеннее то, что этот доступ мутабельный (то есть, обе эти операции – это аксессоры). С их помощью можно не только читать элементы списковой ячейки, но и произвольно менять их. Если в изменении "головы" списковой ячейки ничего принципиально нового нет (т.к. это просто изменение какого-то элемента списка), то изменение его "хвоста" открывает новые возможности.
В большинстве диалектов языка LISP просто примитивами car и cdr не ограничиваются – предусмотрены и многочисленные их довольно сложные композиции (вроде caar, cadr, cdar, cddr и т.п.) В Athanor таких встроенных операций нет (хотя, если они нужны – их совсем нетрудно определить). Но вот возможность многократного применения операций для "головы" и "хвоста" списка полезна очень часто – и для неё есть следующие встроенные функторы:
|
l_head_by (n, List)
|
Применение (n раз подряд) l_head к списку List
|
|
l_tail_by (n, List)
|
Применение (n раз подряд) l_tail к списку List
|
Например: l_head_by (3, List) – эквивалент l_head (l_head (l_head (List))), а l_tail_by (2, List) – эквивалент l_tail (l_tail (List)). Понятно, что когда n == 1 – применение этих операций будет просто равносильно l_head (List) и l_tail (List). Если же вдруг n == 0 – то они обе просто возвращают List. И разумеется, обе эти операции также возвращают мутабельный результат – конечно, если обращаются к существующей списковой ячейке. Если значение n слишком велико – обе операции просто возвращают ().
А теперь покажем, как с помощью этих операций очень легко можно модифицировать списки. Например, если в список List нужно вставить элемент Elem перед позицией n – то это можно сделать так:
Если же нужно удалить фрагмент списка List, длиной m начиная с позиции n – то проще всего сделать так:
Хотя, оба приведённых решения отнюдь не самые оптимальные (хотя бы потому, что вызывают l_tail_by дважды...) – но они работают.
Наконец заметим, что доступ к элементу списка L с индексом n – L[n] – по сути, просто сокращение для l_head (l_tail_by (n, L)).
Рассмотрим теперь подробно присваивание списков. Левый операнд в операции присваивания (set) должен быть мутабельным. В том числе, он может быть списком, состоящим из мутабельных элементов (чаще всего, переменных), причём эти мутабельные списки тоже могут быть вложенными! В простейшем случае – мы просто присваиваем списку переменных список определённых значений:
Здесь сразу три переменные (varA, varB и varC) – получат (соответственно) значения 101, 202 и 303. Конечно, этот пример тривиален, т.к. все значения – константы. Более интересно, когда присваиваются результаты выражений – особенно, когда в их вычислении участвуют уже имеющиеся значения присваиваемых переменных. Для спискового присваивания действует важное правило: все значения (в правой части присваивания) вычисляются до того, как они присваиваются элементам в левой части! Это означает, что чтобы поменять местами значения переменных varA и varB, можно написать просто:
В данном случае, это несколько избыточно. В языке уже есть функтор swap, который делает ту же операцию проще: swap(varA, varB). Однако, бывают ситуации, когда надо поменять местами значения сразу трёх (и даже более) переменных (или других мутабельных). Например:
Здесь значения переменных varA, varB и varC перемещаются циклически (при этом ни одно не теряется). Вот ещё один интересный пример: предположим, что нам надо повернуть (на плоскости) вектор (dX, dY) на угол phi (разумеется, заданный в радианах). Это удобно делать одним присваиванием:
В большинстве языков программирования здесь пришлось бы ввести как минимум одну временную переменную – а вот списковое присваивание позволяет прекрасно обойтись и без неё!
Во всех рассмотренных нами случаях, длина списка в левой части присваивания равна длине списка в правой – но что, если они не совпадают? В принципе, такое тоже бывает. Если список "справа" длиннее, чем список "слева" – все его "избыточные" элементы (т.е. те, для которых не хватило значений) просто опустеют, т.е. получат значение (). Более интересна обратная ситуация! Если список присваиваемых значений длиннее, чем список переменных – то последняя переменная этого списка получит своим значением весь не присвоенный "хвост" списка. Например:
Здесь список присваиваемых значений – на целых два элемента длиннее, чем список переменных, которым его можно присвоить. Так что, в результате получим { A = 10; B = 20; C = [30 40 50]; } То есть, последняя переменная С – получит своим значением не скаляр, а список из всех трёх значений, оставшихся "не присвоенными". Таким образом, после этой операции значением списка [A B C] – станет [10 20 30 40 50], то есть именно то, что мы ему присвоили! Что можно рассматривать, как своего рода инвариант. Или как некое правило: при списковом присваивании ни одно значение не "теряется"! Если для них не осталось значений в левой части присваивания – последняя переменная в ней получит в качестве значения сразу весь "хвост".
Кстати, и обычное списковое присваивание – тоже можно рассматривать как частный случай этой ситуации. Если мы пишем что-нибудь вроде:
– то в левой части у нас список из четырёх значений, а в правой – лишь одна переменная L! А поскольку всегда действует правило "значения теряться не должны", единственный вариант – присвоить весь список ['A' 'B' 'C' 'D'] переменной L (чего мы и ждём). Более того: и левый, и правый операнды присваивания могут быть не простыми списками, а иерархическими (но столь экзотические случаи мы всё же рассмотрим позднее).
Мы так подробно рассматриваем семантику спискового присваивания и потому, что она применяется и во многих других случаях. Например, при обращении к функтору (встроенному, или определённому пользователем) – при передаче ему параметров примерно это и происходит. (Правда, пользовательские функторы мы пока не рассматривали – но довольно скоро перейдём и к ним.)
Пока что, завершим тему иерархических списков одним важным предупреждением. Все явные присваивания "голове" и "хвосту" списковых ячеек – механизм очень мощный, но иногда и довольно опасный! Таким путём легко можно создать, например, зацикленные (или "закольцованные") списки. Большая часть встроенных списковых функторов работать с ними нормально не будет! В общем, это хороший способ выстрелить себе в ногу. К тому же, такие списки не нужны (особенно, с тех пор, как язык явно поддерживает кольца, т.е. кольцевые структуры данных, работа с которыми намного удобнее и безопаснее). Поэтому, используйте низкоуровневые манипуляции со списками – вроде явного присваивания результатам l_head/l_head_by/l_tail/l_tail_by – только когда вы очень хорошо представляете себе, что именно вы делаете, и чего хотите этим добиться! Все рекурсивные структуры данных в этом отношении примерно так же опасны, как и рекурсивные алгоритмы: вся ответственность за то, чтоб рекурсия нормально завершилась, тут лежит в основном на вас.