60 функций PicoLisp. Часть 6: Списки и строки
Перевод. Оригинал здесь
Это девятая часть цикла Введение в PicoLisp и шестая (последняя) часть серии "60 функций PicoLisp".
В этой статье основное внимание будет уделено работе со списками, как главной структуре данных PicoLisp, а также будут кратко рассмотрены функции работы со строками.
Для того, чтобы хорошо понимать работу со списками, нам придётся вернуться в самое начало - к статье Концепции и типы данных PicoLisp (советуем сначала прочесть её, если вы не сделали этого раньше). Как вы узнали из той статьи, в PicoLisp всего три типа данных: числа, символы и списки.
В кратце для самых ленивых: ячейка виртуальной машины PicoLisp состоит из двух 64-битных слов, которые в терминологии LISP традиционно называются CAR и CDR. Эти слова могут либо содержать числовое значение, либо указатель на другую ячейку.
+-----+-----+
| CAR | CDR |
+-----+-----+
Что такое списки? Это последовательность связанных друг с другом ячеек, в которой CDR ячейки содержит указатель на следующую. Вы увидите примеры работы с этими указателями ниже.
Чтобы определить список, его нужно окружить обычными круглыми скобками. вот несколько примеров со списками:
(A) - простой список из одной ячейки. В CAR находится символ A, в
CDR - NIL.
+-----+-----+
| A | NIL | список из одной ячейки
+-----+-----+
(A B C) - список из трёх ячеек. В CAR каждой содержатся символы A,
B и C соответственно, в CDR последней находится NIL.
+-----+-----+
| A | | |
+--+--+-----+
|
V
+-----+-----+
| B | | |
+--+--+-----+
|
V
+-----+-----+
| C | NIL |
+-----+-----+
(A B) - точечная пара, также часто называемая "cons pair" - список
из единственной ячейки, CAR которой содержит символ A, а CDR - символ
B.
+-----+-----+
| A | B | точечная пара
+-----+-----+
Также списки могут быть вложенными, то есть элементом списка может быть список.
Самыми базовыми функциями доступа к элементам списка являются car и
cdr.
car возвращает первый элемент списка:
: (car (1 2 3 4 5 6))
-> 1
cdr возвращает весь список за исключением первого элемента.
Фактически, функция cdr берёт указатель из CDR первой ячейки. Он
указывает на следующую ячейку, благодаря чему можно получить весь
остаток списка.
: (cdr (1 2 3 4 5 6))
-> (2 3 4 5 6)
Есть несколько сокращений для комбинаций из функций car и cdr.
Например, если мы хотим получить второй элемент списка, то сначала мы
применяем к списку функцию cdr, получая все элементы кроме первого, а
затем car, возвращающую первый элемент этого остатка. Сокращение такой
комбинации действий записывается как cadr:
: (cadr (1 2 3 4 5 6))
-> 2
(car (cdr (1 2 3 4 5 6))) # эквивалент
-> 2
Если у нас первым элементом списка идёт вложенный список, то применив
функцию cdar мы получим все элементы такого подсписка, кроме первого:
: (cdar '((1 2) 3 4 ))
-> (2)
(cdr (car '((1 2) 3 4))) # эквивалент
-> (2)
Первый элемент первого вложенного списка извлекается функцией caar:
: (caar '((1 2) 3 4))
-> 1
Этот принцип сокращённых функций действителен для всех сочетаний букв
a и d вплоть до четырёх. Вот полный список таких сокращений:
caaaar, caaadr, caaar, caadar, caaddr, caadr, caar,
cadaar, cadadr, cadar, caddar, cadddr, caddr, cadr, car,
cdaaar, cdaadr, cdaar, cdadar, cdaddr, cdadr, cdar,
cddaar, cddadr, cddar, cdddar, cddddr, cdddr, cddr.
Пользоваться такими функциями бывает не очень удобно, поэтому для
облегчения доступа к элементам списков в PicoLisp есть функция nth.
Эта функция принимает на вход список и одно или несколько чисел,
возвращая "хвост" (CDR) соответствующего списка:
: (nth '(a b c d) 2)
-> (b c d)
: (nth '(a (b c) d) 2 2)
-> (c)
Так что достаточно сочетать nth и car, чтобы получить любой элемент
списка.
Если вам нужен список из последовательно возрастающих или уменьшающихся
чисел, то вы можете воспользоваться функцией range. Она принимает на
вход начальное число, конечное число и опционально - шаг между соседними
числами:
: (range 1 6)
-> (1 2 3 4 5 6)
: (range 6 1)
-> (6 5 4 3 2 1)
: (range -3 3)
-> (-3 -2 -1 0 1 2 3)
: (range 3 -3 2)
-> (3 1 -1 -3)
Для более сложных случаев инициализируется процесс построения списка с
помощью функций make, которая инициализирует процесс, link, которая
добавляет элементы в конец списка и yoke, которая добавляет элементы в
начало. Указатели на начало и конец создаваемого списка хранятся и
обрабатываются на уровне машинных кодов, что позволяет быстро строить
даже очень длинные списки.
: (make (link 1) (link 2 3) (link 4))
-> (1 2 3 4)
: (make (link 2 3) (yoke 1) (link 4))
-> (1 2 3 4)
Альтернативным способом создания списков является использование функции
cons. Она берёт пустую ячейку и помещает первый поданный аргумент в
CAR ячейки, а второй - в её CDR. В этом важное отличие cons от link,
которая помещает новый элемент не в CDR ячейки, а в конец всего списка.
Если подать функции cons больше двух аргументов, то она будет
соединять их последовательно. Выражение (cons 'a 'b 'c 'd)
эквивалентно выражению (cons 'a (cons 'b (cons 'c 'd))).
: (cons 1 2)
-> (1 . 2)
: (cons 'a '(b c d))
-> (a b c d)
: (cons '(a b) '(c d))
-> ((a b) c d)
: (cons 'a 'b 'c 'd)
-> (a b c . d)
length возвращает "длину" списка, рассчитывая её исходя из
количества ячеек. Если на вход length подаётся не список, а число,
то она возвращает количество цифр в числе (добавляя ещё единицу для
отрицательных чисел). Для символов она возвращает количество букв в
имени.
# List
: (length (1 (2) 3))
-> 3
: (length (1 . 2))
-> 1
# Symbol
: (length "abc")
-> 3
# Number
: (length 123)
-> 3
Обычным требованием является применение функции к каждому элементу списка. Ниже приведено несколько функций, которые это делают.
apply применяет функцию к списку. При этом, если поданы дополнительные
аргументы, они передаются функции первыми.
: (apply + (1 2 3))
-> 6
: (apply '((X Y Z) (* X (+ Y Z))) (3 4 5))
-> 27
: (apply println (3 4) 1 2)
1 2 3 4
-> 4
mapcar применяет функцию к каждому элементу переданного ей списка. В
отличие от apply, которая передаёт список в функцию целиком, mapcar
передаёт список поэлементно. Возвращает функция весь обработанный список
целиком.
Если в mapcar подаётся больше одного списка, то элементы второго и
последующих списков подаются в функцию как второй и последующие
аргументы.
: (mapcar sqrt (4 9 16))
-> (2 3 4)
: (mapcar + (1 2 3) (4 5 6))
-> (5 7 9)
: (mapcar + (1 2 3) 5)
-> (6 7 8)
: (mapcar + (1 2 3) (1 2))
-> (2 4 NIL)
mapcar с анонимной функцией:
# add element of first list to square of element of second list
: (mapcar '((X Y) (+ X (* Y Y))) (1 2 3 4) (5 6 7 8))
-> (26 38 52 68)
mapc очень похожа на mapcar, но возвращает не весь обработанный
список, а только последнее вычисленное значение.
: (mapc println (1 2 3 4) '(A B C))
1 A
2 B
3 C
4 NIL
-> NIL
Кратко остановимся на функциях работы со строками.
pack преобразует поданные аргументы в строку. При этом символ
преобразуется в своё имя, число в своё строковое представление, список
преобразуется поэлементно.
: (pack 'car " is " 1 '(" symbol " name))
-> "car is 1 symbol name"
chop преобразует длинную строку в список однобуквенных строк:
: (chop 'car)
-> ("c" "a" "r")
: (chop "Hello")
-> ("H" "e" "l" "l" "o")
char преобразует число в соответствующий символ в кодировке unicode
и наоборот - символ в число:
: (char 100) # Convert unicode to symbol
-> "d"
: (char "d") # Convert symbol to unicode
-> 100
Поздравляем! Теперь вы знаете, как работают более 60 функций языка PicoLisp.
В следующей статье будет кратко рассмотрена арифметика чисел с фиксированной точкой. После этого мы вместе напишем первую программу на замечательном языке PicoLisp. Последняя статья цикла для начинающих будет посвящена пользованию справкой и отладчиком.