Первый шаг к пониманию этой проблемы состоит в том, чтобы четко указать, из чего состоят данные, с которыми мы работаем. Запишем серию определений данных:
;; 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 в записях, мы просто хотим, чтобы любые ZIP s соответствовали остальной части списка. Глядя на контракт для 'find', мы видим, что вызов 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.
Удачи!