返回計劃列表

Question

我想解決Scheme（R5RS）中的問題。以下是我的示例數據：

(define zipcodes '(
(96774 ookala hawaii) 
(90001 losangeles california) 
(90263 malibu california) 
(10044 newyork newyork) 
)) 

每個列表元素的格式爲(ZIP CITY STATE)。我想創建一個像這樣工作的函數：將STATE作爲輸入，並且該函數返回此狀態的zipcode（如果沒有該狀態的元素，則返回空列表）。

>(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。

Answer 1

首先，您發佈的代碼中存在拼寫錯誤：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，但是不同參數取決於元素是否被找到。你怎麼能這樣做？ （提示：您需要第三個參數。）

Answer 2

瞭解這個問題的第一步是明確說明我們正在處理的數據由什麼組成。讓我們寫下了一系列的數據定義的：

;; A ZIP is a number 
;; A CITY is a symbol 
;; A STATE is a symbol 

的ENTRY是ZIP，一個CITY和STATE的列表。回想一下，列表是一系列以null結尾的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 

讓我們先處理第二種情況。在情況下，我們要搜索中的條目不匹配，在未來ENTRY的STATE的STATE我們只是想匹配列表中的其他任何ZIP秒。看看'找到'的合同，我們可以看到，在列表的其餘部分找到正確的東西將會給我們我們想要的東西！灌裝，在我們有：

;; 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 

在第一種情況下，我們知道，在「entires」第一ENTRY具有我們正在尋找的STATE相匹配的狀態。考慮一下，我們希望爲我們的最終結果在這種情況下：我們希望能有名單與我們已經知道了ZIP開始匹配我們正在尋找跟任何其他ZIP s的狀態也匹配的entries其餘STATE 。我們可以使用cons來構建一個新的列表。 cons有如下合同：

;; cons : any [listof any] -> [listof any] 

的第一個參數cons很簡單。我們再假設我們有一個函數'get-zip'，該函數給出了給定ENTRY的ZIP。然後，我們可以簡單地提取從ENTRY的ZIP：

;; 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)) 

在解決這個問題，我們利用「設計方」，一步一步的指導，以設計方案的元素。 Felleisen，Findler，Flatt和Krishnamurthi在「如何設計程序」中全面概述了「設計食譜」。全文可在線獲取：www.htdp.org。

祝你好運！