Все списки, с которыми вы имели дело до этого момента, либо создавались с помощью литералов и функции 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
Имена этих функций таковы по историческим причинам (подробнее вы можете почитать в Википедии), но большинство лиспоподобных языков предоставляют их для единообразия.
Итак, у нас есть пары, но когда же они становятся списками? Список — пара из первого сохраняемого значения, называемого головой (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
: они будут возвращать "голову" и "хвост" списка. Однако в 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
Если вы зашли в тупик, то самое время задать вопрос в «Обсуждениях». Как правильно задать вопрос:
Тесты устроены таким образом, что они проверяют решение разными способами и на разных данных. Часто решение работает с одними входными данными, но не работает с другими. Чтобы разобраться с этим моментом, изучите вкладку «Тесты» и внимательно посмотрите на вывод ошибок, в котором есть подсказки.
Это нормально 🙆, в программировании одну задачу можно выполнить множеством способов. Если ваш код прошел проверку, то он соответствует условиям задачи.
В редких случаях бывает, что решение подогнано под тесты, но это видно сразу.
Создавать обучающие материалы, понятные для всех без исключения, довольно сложно. Мы очень стараемся, но всегда есть что улучшать. Если вы встретили материал, который вам непонятен, опишите проблему в «Обсуждениях». Идеально, если вы сформулируете непонятные моменты в виде вопросов. Обычно нам нужно несколько дней для внесения правок.
Кстати, вы тоже можете участвовать в улучшении курсов: внизу есть ссылка на исходный код уроков, который можно править прямо из браузера.
Ваше упражнение проверяется по этим тестам
1#lang racket
2
3(require (only-in rackunit check-equal? test-begin))
4(require "index.rkt")
5
6(test-begin
7 (check-equal? (lookup "foo" null) #f)
8
9 (check-equal?
10 (lookup "foo" (list (cons "foo" "bar")))
11 (cons "foo" "bar"))
12
13 (check-equal?
14 (lookup "foo" (list (cons "bar" "foo")))
15 #f)
16
17 (check-equal?
18 (lookup 42 (list (cons 42 0)
19 (cons 30 0)
20 (cons 42 100500)))
21 (cons 42 0)))
22
Решение учителя откроется через: