Программирование на Athanor – 11 (дополнительные списковые операции)

Операции над списками с функциональными операндами

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

Однако (прежде, чем подробно рассматривать эти операции), упомянем пару операций, которые позволяют довольно просто вставлять/удалять элементы списка:

Прежде всего заметим, что эти операции работают с началом списка List (в отличие от Perl или JavaScript, где функции push/pop выполняют изменения в конце списка). Другими словами, эти операции работают со списком List как со стеком, самая вершина которого находится в его начале. (Если помните: унарные и бинарные скалярные операции рассматривают списки примерно так же.)

Операция [<-] (она же l_push) осуществляет вставку элементов в начало списка List, извлекая их значения последовательно из списка FromList. (Таким образом, в List они заносятся в порядке, обратном их порядку в FromList!) Например:

• List = [1 2 3 4];
• List [<-] [5 6 7 8];

   В результате список List получит значение (8, 7, 6, 5, 1, 2, 3, 4). Любой элемент из списка добавляемых значений сам может быть списком (но если последний элемент FromValues является списком – FromValues должен быть открытым). В частности, если нужно вставить список (например, ['aa' 'bb' 'cc']) как один элемент, это делается примерно так:

• List [<-] (['aa' 'bb' 'cc'], );

Обратная операция [->] (она же l_pop) извлекает элементы из начала списка List, и записывает их в список ToMutables, элементы которого должны быть мутабельными выражениями. (Чаще всего это, конечно, переменные.) Например:

• List [->] [a b c d];

В результате, список List вернется к (исходному) значению (1, 2, 3, 4), а другие переменные примут такие значения: a == 8, b == 7, c == 6, d == 5. Ни одно значение из оригинального списка не пропадет!

Обе эти операции (как и многие другие), рассматривают скалярные значения и () – как «вырожденные» варианты списков длины 1 и 0. Например, если исходное значение List пусто, т.е. (), вставка в него произвольного значения просто эквивалентна присваиванию этого значения List. Если List уже содержит скалярное значение Tail, после выполнения List [<-] Head значением List станет (Head, Tail). Разумеется, справедливо и обратное: если из двухэлементного списка извлечь один элемент, в списке останется последний элемент (если он скалярный – список превратится в скаляр). Если же из скалярной переменной "извлечь" ее значение, она станет равна (). (Понятно, что из () извлечь уже ничего нельзя.)

Сочетание операций l_push/l_pop с l_tail_by позволяет вставлять или удалять элементы в произвольном месте списка. Например, если L = (1, 2, 3, 4, 5), то после выполнения:

• l_tail_by (3, L) [<-] "+++";

– список L станет равен (1, 2, 3, "+++", 4, 5). Если после этого выполнить:

• l_tail_by (2, L) [->] [x y z];

   – то список L станет равен (1, 2, 5); а переменные: x = 3, y = "+++", z = 4. В общем, идея должна быть понятна.

Через l_tail_by можно вставить новые элементы перед любым существующим элементом закрытого списка. Если список открытый – новые значения можно вставить и в самый его конец (это ещё одно преимущество открытых списков). Рассмотрим теперь ещё одну операцию, которая позволяет "разрезать" список на части.

Функтор l_split «разрезает» список List таким образом, что его «головной» фрагмент содержит (внимание!) n+1 элемент, а «хвостовой» – все остальные. Разумеется, эта операция является мутатором для списка List. Впрочем, если n == 0, то ничего не происходит, и список вообще не изменяется (понятно, почему?)

Например, когда:

• ll = ['a' 'b' 'c' 'd' 'e' 'f'];

– после выполнения l_split(3, ll) – значение списка ll станет равным (('a', 'b', 'c', 'd'), 'e', 'f'). Другоми словами, l_head(ll) станет равно ('a', 'b', 'c', 'd'), а l_tail(ll) – ('e', 'f'). Заметим, что эта операция (в некотором роде) является обратной для l_cat (списковой конкатенации) – вызов:

• l_cat^l_split (n, List);

– просто возвращает "прежнее" значение списка List для любого n. (Понятно, почему?)

Заметим, что вот так легко можно определить: является ли список-операнд открытым или закрытым?

• ! is_open_list (L) = is_list^l_tail_by (#L - 1, L);

Вызов is_open_list возвращает 1, если его операнд-список является открытым (и 0, в противном случае).

А теперь перейдём к списковым функторам, имеющим своими операндами функциональные ссылки. Начнём с принимающих ссылки на предикаты. Как и в случае со строками, введём немного полезных терминов: будем называть элемент списка Pred-негативным (если применение к нему предиката Pred возвращает 0) или Pred-позитивным (в противном случае).

Вот альтернативная формулировка: возвращается индекс для самого первого Pred-негативного (l_while) или Pred-позитивного (l_until) элемента. В граничных случаях: l_while возвращает 0 (если Pred-негативен самый первый элемент List) или #List (если ВСЕ элементы списка Pred-позитивны). Для l_until "негативность" и "позитивность" меняются местами. В общем, это аналоги строковых операций s_span_in и s_span_ex (только для списков).

Аналогично l_while и l_until, только действуют не с начала списка List, а с его конца. В граничных случаях: l_while_r возвращает #List (если Pred-негативен самый последний элемент List) или 0 (если ВСЕ элементы списка Pred-позитивны). Для l_until_r "негативность" и "позитивность" меняются местами. (По своей функции, это "списковые" аналоги строковых операций s_rspan_in и s_rspan_ex.)

Вот несколько примеров:

• l_while (!(V) = (V <= 3), List)

Возвращает индекс первого элемента в List, строго большего 3 (предполагая, что все элементы списка – числа).

• l_until (!(V) = (V <= 3), List)

Наоборот: индекс первого элемента в List, меньшего или равного 3.

• l_while_r (!(V) = (V > 5), List)

Индекс первого с конца элемента в List, строго большего 5.

• l_until_r (!(V) = (V > 5), List)

Наоборот: индекс первого с конца элемента в List, меньшего или равного 5.

Рассмотренные ниже функторы – уже действуют на весь список, и позволяют выбрать из него элементы по некому критерию (заданному предикатом):

Вот примеры:

• l_filter_in (!(V) = (abs (V) < 10), List)

Результат – список из всех элементов List (положительных или отрицательных), абсолютная величина которых строго меньше 10.

• l_filter_ex (!is_string, List)

Результат – список из всех элементов List, которые не являются строками.

Следующие операции подсчитывают элементы в списке по заданному критерию:

Эти четыре функтора связаны очевидными тождествами:

• # l_filter_in (Pred, List) == l_count_in (Pred, List)
• # l_filter_ex (Pred, List) == l_count_ex (Pred, List)

Рассмотрим теперь операции, позволяющие конструировать списки. Например, l_map реализует отображение одного списка на другой:

Операция применяет функциональную ссылку Func (это уже не обязательно предикат!) к элементам списка List, возвращая список из полученных результатов. Вот несколько примеров:

• l_map (! (x) = (x * 3), List)

Это возвращает результат поэлементного умножения списка List на 3 (предполагая, что все его элементы – числовые, или к ним приводятся). Например, если List = (10, 25, 30) – то результатом будет список (30, 75, 90).

• l_map (! (s) = (#$ s), List)

Возвращает список из строковых длин элементов списка List (предполагая, что они все строки, или к ним приводятся). Например, если List = ('alpha', 'beta', 'gamma') – то результатом выполнения будет список (5, 4, 5).

• l_map (! (str) = (s_filter_ex (str, ! cc_blank)), List)

Возвращает список элементов (также молча предполагая, что все они строковые!) списка List с "вычищенными" из них пробелами (и всеми прочими пробельными символами, позитивными для предиката cc_blank).

Результат l_map всегда имеет ту же длину, что и список-операнд List. Более того, l_map сохраняет такой атрибут списка как его "открытость": если список List открытый – то и результат тоже будет открытым списком. По обычной логике, если операнд List окажется скаляром, то возвращается просто значение (Func ! List), а если операнд равен () – то и значением будет ().

Следующие две операции трансформируют произвольный диапазон значений в список:

Понятие "диапазона" мы уже рассматривали (и не раз), но повторим: From..To задаёт все целые числа от (включая!) нижней границы From до (не включая!) верхней границы To. Функтор l_range превращает этот диапазон в возрастающий список содержащихся в нём значений (от From до To-1); l_range_r делает то же самое, но по убыванию (от To-1 до From). Если задан функциональный аргумент Func – то он применяется к каждому из значений, и возвращается уже список из полученных результатов. Если же Func не задан – это не ошибка, и возвращается просто сам список целых чисел в диапазоне.

Заметим, что в этом случае запятая в списке не должна быть опущена! (Без неё, список From..To будет восприниматься не как один аргумент, а как два, что некорректно!) Вот примеры:

• l_range (15..20, )

Результат: список (15, 16, 17, 18, 19).

• l_range_r (15..20, )

Результат: список (19, 18, 17, 16, 15).

• l_range (15..20, !(n) = (2*n - 1))

Результат: список (29, 31, 33, 35, 37).

• l_range_r (15..20, !(n) = (2*n - 1))

Результат: список (37, 35, 33, 31, 29).

Правда, что второй операнд в l_range/l_range_r (отчасти) избыточен. Можно было бы ограничиться одним только диапазоном, а для его преобразований явно использовать l_map:

• l_range (Range, Func) – эквивалентно l_map (Func, l_range (Range, ))
• l_range_r (Range, Func) – эквивалентно l_map (Func, l_range_r (Range, ))

Но первый вариант вызова предпочтительней, так как он существенно эффективней (особенно, когда список длинный). И его эффективность – главная причина, ради которой этим функторам можно передать второй (необязательный) аргумент. А первый (т.е. диапазон) может оказаться и пустым (если From >= To), но в этом случае (вполне ожидаемо) результатом тоже будет пустота, т.е. ().

Скажем, вот так можно преобразовать строку в список кодов символов, из которых она состоит:

• ! str_chars (S) = l_range (#$ S, !(I) = s_ord (S, I));

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

Другими словами:

• inside (Value, From..To)
  – эквивалентно (From <= Value && Value < To)
• outside (Value, From..To)
  – эквивалентно (Value < From || Value >= To)

Это всё справедливо, когда диапазон осмысленный (т.е. непустой). Если же он пустой, то inside и outside являются просто синонимами для false и true соответственно.

Функтор l_cmp очень полезен для сравнения двух списков:

Первый операнд для F_Compare должен быть ссылкой на компаратор: бинарный функтор, сравнивающий два своих операнда, и возвращающий целое число. Если это число отрицательное – первый элемент считается "меньшим", чем второй; если оно положительное – первый элемент считается "большим", чем второй; если оно равно нулю – оба элемента считаются "равными". Разумеется, можно использовать и встроенные компараторы: например, cmp – сравнивает два произвольных числа (см. статью 1), а s_cmp – сравнивает две строки "словарно" (см. статью 2). Для менее тривиальных сравнений, можно определить и любой свой собственный компаратор. Сравнение происходит так: списки LeftList и RightList сравниваются поэлементно, до тех пор, пока результат применения F_Compare равен нулю (или пока какой-то список не "кончится"). Если F_Compare вернёт ненулевой результат – процесс завершается, и он им будет результатом всей операции. Если F_Compare вернул нулевое значение для всех пар существующих элементов, результат определяется тем, в каком из списков остались "лишние" элементы. Если LeftList длиннее RightList – возвращается 1; если LeftList короче RightList – возвращается -1; и только если длины списков равны (и все их элементы тоже были попарно "равны") – возвращается 0. Понятно, что сама l_cmp также является компаратором – так что, вложенные списки с её помощью можно сравнивать рекурсивно.

Другими словами, l_zip строит список из пар элементов своих списков-операндов, вот так:

• ((LeftList[0], RightList[0]), (LeftList[1], RightList[1]), (LeftList[2], RightList[2]), ... ,)

что альтернативно можно записать и так:

• (LeftList[0]::RightList[0], LeftList[1]::RightList[1], LeftList[2]::RightList[2], ..., )

Результатом всегда является открытый список. Если какой-нибудь из списков-операндов длиннее другого, то результат тоже будет иметь такую длину, просто один из компонентов ("голова" или "хвост") в его элементах будет иметь значение (). Понятно, что если длины списков равны – результат будет иметь ту же длину. Например:

	l_zip ((1, 2, 3, 4), ('a', 'b', 'c', 'd'))

– возвращает список:

	((1, 'a'), (2, 'b'), (3, 'c'), (4, 'd'), )

А применяя l_map к результату l_zip – нетрудно применить попарно к двум спискам произвольный бинарный функтор! Например, l_map (! add, l_zip (LeftList, RightList)) – возвращает поэлементную сумму списков LeftList и RightList (конечно, предполагая, что списки состоят из числовых (или, хотя бы, скалярных) элементов, и они имеют равную длину). Сама l_zip комбинирует только два списка – но её вызовы могут быть вложенными: например, l_zip (ListA, l_zip (ListB, ListC)) – поэлементно комбинирует три списка ListA, ListB и ListC. К каждому из результатов, в свою очередь, может быть применён l_map: это позволяет применить произвольный тернарный функтор к трём списками, или кватернарный к четырём спискам... в общем, дальнейшее понятно.

Этот обзор не исчерпывает всего набора списковых операций (например, не рассмотрена сортировка списков). Но ограничимся пока этим, поскольку статья и так получилась довольно объёмной. И уже со всеми рассмотренными списковыми операциями – можно делать много полезного.