Racket: Внутреннее устройство списков, пары, cons, null

Все списки, с которыми вы имели дело до этого момента, либо создавались с помощью литералов и функции list, либо являлись результатами вычисления каких-то выражений. Во всех этих случаях список выглядит как нечто неделимое, цельное. Именно так работает абстракция: для работы со списками достаточно думать о списке, как о самостоятельной и самодостаточной сущности!

Тем из вас, кто сталкивался в других языках с массивами, могло показаться, что в Racket списки — это те же массивы: отдельные участки памяти компьютера, хранящие все значения рядом.

На самом же деле во всех языках семейства Lisp, да и в большинстве других языков, располагающих к функциональному подходу, списки — это цепочки вложенных пар. А вот пара уже является неделимой структурой. И чтобы понять списки, нужно сначала освоить пары.

Пары

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

(cons 1 2)         ; '(1 . 2)
(pair? (cons 1 2)) ; #t

Обратите внимание на то, как отображается полученное значение: элементы пары разделяет точка ("."). Такое отображение не даёт спутать пару со списком '(1 2).

Как и в случае со списками, кавычка здесь означает цитирование. Вы можете попробовать по-создавать пары с помощью такого синтаксиса, но мы рекомендуем использовать функцию cons, как более простой в использовании вариант.

Для доступа к элементам пары используются функции car и cdr (читаются как "кар" и "кадр"):

(define p (cons "Bob" 42))

(car p) ; "Bob"
(cdr p) ; 42

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

cons + null

Итак, у нас есть пары, но когда же они становятся списками? Список — пара из первого сохраняемого значения, называемого головой (head), и другого списка, называемого хвостом (tail). Вот как можно собрать список вручную:

(cons 1 (cons 2 (cons 3 null))) ; '(1 2 3)

В последней паре справа располагается специальное значение null, означающее список нулевой длины. Пустой список можно обозначить и другими способами, функция проверки на пустоту empty? вернёт #t для любого варианта:

(empty? null)   ; #t
(empty? (list)) ; #t
(empty? '())    ; #t

Стоит ещё раз подчеркнуть, что не любая пара является списком. Второй элемент пары должен сам быть списком, пусть даже пустым — только тогда эта пара тоже будет считаться списком! Вот несколько примеров разных пар:

(pair? (cons 1 2))            ; #t
(list? (cons 1 2))            ; #f - справа не список

(pair? (cons 1 null))          ; #t
(list? (cons 1 null))          ; #t - тут всё понятно

(pair? (cons 1 (cons 2 3)))   ; #t
(list? (cons 1 (cons 2 3)))   ; #f - хвост не является списком!

(list? (cons 1 (cons 2 null))) ; #t - всё хвосты являются списками

car/cdr и first/rest

Для списков, как и для любых других пар, можно использовать функции car и cdr: они будут возвращать "голову" и "хвост" списка. Однако в Racket есть более подходящие средства для работы именно со списками: функции first и rest.

first и rest проще читать уже благодаря их именам, но самое важное свойство этих функций заключается в том, что они отказываются работать с не-списками: вы получите ошибку, если примените любую из этих функций к паре, не содержащей список справа.

(first (cons 1 2))
; first: contract violation
;   expected: (and/c list? (not/c empty?))
; ...
(rest (cons 1 2))
; rest: contract violation
;   expected: (and/c list? (not/c empty?))
; ...

Обе ошибки говорят о том, что функции ожидают аргумент, удовлетворяющий условию (and/c list? (not/c empty?)), которое можно прочитать как "list? И НЕ empty?" или "список И НЕ пустой". Весьма логично!

Такая разборчивость помогает в отладке, а если использовать Typed Racket — вариант языка Racket, использующий проверку типов, — то вы получите ошибку типизации вместо ошибки во время исполнения.

Задание

Реализуйте функцию lookup, которая должна принимать аргумент-ключ и список пар "ключ-значение" и возвращать либо пару "ключ-значение", где ключ равен первому аргументу, либо #f, если подходящих пар в списке не нашлось. Если подходящих пар найдётся несколько, вернуть нужно первую.

Примеры:

(define user-ages
  (list (cons "Tom" 31)
        (cons "Alice" 22)
        (cons "Bob" 42)))

(lookup "Bob" user-ages) ; '("Bob" . 42)
(lookup "Tom" user-ages) ; '("Tom" . 31)
(lookup "Moe" user-ages) ; #f