Возврат списка в схеме
Я хочу решить проблему в Схеме (R5RS). Вот мои примеры данных:
(define zipcodes '(
(96774 ookala hawaii)
(90001 losangeles california)
(90263 malibu california)
(10044 newyork newyork)
))
Каждый элемент списка имеет форму (ZIP CITY STATE), Я хочу создать функцию, которая работает следующим образом: передать STATE в качестве ввода, и функция возвращает почтовые индексы этого состояния (возвращает пустой список, если для этого состояния нет элемента).
>(findzips 'california)
(90001 900263)
>(findzips 'berlin)
empty
Я пытаюсь это с помощью кода ниже, но он возвращает только первое значение, а не список
(define (findzips x)
(find x zipcodes))
(define find
(lambda (x zipcodes)
(if (EQ? x (caddr (car zipcodes)))
(list (car (car zipcodes)))
(find x (cdr zipcodes)))))
Мне не разрешено использовать ! функции или let ,
2 ответа
Во-первых, в коде, который вы разместили, есть опечатка: find3 должно быть find,
Давайте посмотрим на эту функцию с правильным отступом:
(define find
(lambda (x zipcodes)
(if (EQ? x (caddr (car zipcodes))) ; if the current entry matches
(list (car (car zipcodes))) ; then return it, in a single-element list
(find x (cdr zipcodes))))) ; else return the subsequent matches
Если текущая запись совпадает, вы не пытаетесь искать какое-либо последующее совпадение. Таким образом, возвращаемый вами список никогда не будет содержать более одного элемента.
Вам всегда нужно искать последующие элементы, т.е. вам всегда нужно звонить (find x (cdr zipcodes)), Хороший способ будет позвонить let, но ваши домашние задания это исключают. Вы можете просто дублировать вызов. Вместо того, чтобы сделать одноэлементный список с list Процедура, построить список, состоящий из текущего совпадения, за которым следует список последующих совпадений. Процедура добавления одного элемента в список cons,
(define find
(lambda (x zipcodes)
(if (EQ? x (caddr (car zipcodes))) ; if the current entry matches
(cons (car (car zipcodes)) ; then return it, followed by…
(find x (cdr zipcodes))) ; … the subsequent matches
(find x (cdr zipcodes))))) ; else return the subsequent matches
Это не закончено: вы заметите, что эта функция всегда выдает исключение. Вы измельчаете список, в конце концов достигаете конца... и задыхаетесь, потому что вы не обрабатываете случай, когда список пуст. Я оставлю это как упражнение.
Теперь есть другие способы написания этой функции (на самом деле, более эффективные, но более сложные для начинающего). Они могут или не могут быть тем, что было задумано в вашем назначении. Представьте, что вам нужен только один рекурсивный вызов find, и нет let или любой другой способ сохранить результат вызова find, Тогда у вас нет выбора, кроме как позвонить find, но с разными аргументами в зависимости от того, был ли найден элемент или нет. Как ты можешь это сделать? (Подсказка: вам понадобится третий аргумент.)
Первый шаг к пониманию этой проблемы состоит в том, чтобы четко указать, из чего состоят данные, с которыми мы работаем. Запишем серию определений данных:
;; A ZIP is a number
;; A CITY is a symbol
;; A STATE is a symbol
ENTRY это список ZIP, CITY и STATE, Напомним, однако, что список - это серия cons-ячеек, оканчивающихся на ноль. Давайте напишем наше определение данных для ENTRY используя явные вызовы cons:
;; An ENTRY is of the form (cons ZIP (cons CITY (cons STATE null)))
;; A [listof ENTRY] is either:
;;
;; 1. The empty list, null, or
;; 2. (cons ENTRY [listof ENTRY])
С этими определениями данных легче быть точным в том, что мы хотим, чтобы наша функция выполняла. Мы напишем контракт для нашей функции, состоящий из двух частей: имя функции и тип данных, которые использует функция, и виды данных, которые создает функция. Например:
;; <FUNCTION NAME> : <WHAT OUR FUNCTION CONSUMES> -> <WHAT OUR FUNCTION PRODUCES>
Теперь мы можем написать контракт для функций, которые мы хотим написать:
;; find : STATE [listof ENTRY] -> [listof ZIP]
;; Produces the ZIPs in [listof ENTRY] that match the given STATE.
(define (find state entries)
...)
;; findzips : STATE -> [listof ZIP]
;; Produces the ZIPs in 'zipcodes' that match the given STATE.
(define (findzips state)
...)
Давайте начнем заполнять определение для find, Из нашего контракта мы знаем, что "find" принимает два аргумента: STATE и [listof ENTRY], Мы знаем из определения данных для [listof ENTRY] что это может быть одна из двух вещей: (cons ENTRY [listof ENTRY]) или же null, Каждый раз, когда нам приходится обрабатывать более одного случая, мы можем использовать cond к поведению, которое мы хотим в каждом случае:
;; find : STATE [listof ENTRY] -> [listof ZIP]
;; Produces the ZIPs for which there is an ENTRY in the [listof ENTRY]
;; with a STATE that matches the one given.
(define (find state entries)
(cond ((null? entries) ...)
(else ...)))
Обратитесь к своему учебнику или спросите своего инструктора, если cond Вам незнакомо.
Все идет нормально. Так что же должна возвращать наша функция, если она называется null (допустимый входной файл с учетом нашего контракта)? Наш контракт предполагает, что мы должны вернуть пустой список взамен.
;; find : STATE [listof ENTRY] -> [listof ZIP]
(define (find state entries)
(cond ((null? entries) null)
(else ...)))
Все идет нормально. Теперь о трудной части. Если список ввода не пуст, то он должен содержать хотя бы один ENTRY, Для любого данного ENTRY мы должны обработать два случая: либо состояние в записи соответствует STATE мы ищем или нет. Давайте представим, что у нас есть функция, get-state что, учитывая ENTRY, дает нам свое STATE,
;; find : STATE [listof ENTRY] -> [listof ZIP]
(define (find state entries)
(cond ((null? entries) null)
(else (if (equal? state
(get-state (car entries)))
... ;; matches
...)))) ;; doesn't match
Давайте сначала разберемся со вторым случаем. В случае, когда STATE мы ищем не соответствует STATE В следующий ENTRY в записях мы просто хотим любой ZIPs, которые соответствуют в остальной части списка. Глядя на контракт для поиска, мы видим, что вызов find в остальной части списка даст нам именно то, что мы хотим! Заполняя это у нас есть:
;; find : STATE [listof ENTRY] -> [listof ZIP]
(define (find state entries)
(cond ((null? entries) null)
(else (if (equal? state
(get-state (car entries)))
... ;; matches
...)))) ;; doesn't match
В первом случае мы знаем, что первый ENTRY в 'entires' имеет состояние, которое соответствует STATE мы ищем. Рассмотрим, что мы хотим для нашего конечного результата в этом случае: нам бы хотелось, чтобы список начинался с ZIP что мы уже знаем, соответствует STATE мы ищем, а затем любой другой ZIPс состояниями, которые также совпадают в остальных entries, Мы можем использовать cons построить новый список. cons имеет следующий контракт:
;; cons : any [listof any] -> [listof any]
Первый аргумент cons это просто. Давайте снова предположим, что у нас есть функция 'get-zip', которая дает нам ZIP для данного ENTRY, Затем мы могли бы просто извлечь ZIP от ENTRY:
;; find : STATE [listof ENTRY] -> [listof ZIP]
(define (find state entries)
(cond ((null? entries) null)
(else (if (equal? state
(get-state (car entries)))
(cons (get-zip (car entries))
...)
(find state (cdr entries))))))
Второй аргумент cons Я оставлю тебе это упражнение.
Мы почти закончили! Теперь, когда у нас есть find пишу findzips тривиально. Мы просто звоним find с учетом STATE а также zipcodes в качестве своих аргументов. Заполните оставшиеся эллипсы, и вы закончите:
;; get-zip : ENTRY -> ZIP
;; Produces the ZIP for a given ENTRY.
(define (get-zip entry)
...)
;; get-state : ENTRY -> STATE
;; Produces the STATE for a given ENTRY.
(define (get-state entry)
...)
;; find : STATE [listof ENTRY] -> [listof ZIP]
;; Produces the ZIPs in [listof ENTRY] that match the given STATE.
(define (find state entries)
(cond ((null? entries) null)
(else (if (equal? state
(get-state (car entries)))
(cons (get-zip (car entries))
...)
(find state (cdr entries))))))
;; findzips : STATE -> [listof ZIP]
;; Produces the ZIPs in 'zipcodes' that match the given STATE.
(define (findzips state)
(find state zipcodes))
При решении этой проблемы мы использовали элементы "Design Recipe", пошагового руководства по разработке программ. "Рецепт дизайна" полностью описан в "Как разрабатывать программы" Феллайзена, Финдлера, Флатта и Кришнамурти. Полный текст доступен на сайте: www.htdp.org.
Удачи!