Returning a list in scheme

I want to solve a problem in Scheme (R5RS). Here's my sample data:

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

Each list element has the form (ZIP CITY STATE). I want to crea开发者_如何学JAVAte a function that works like this: pass STATE as an input, and the function returns the zipcodes of this state (returns an empty list if there is no element for this state).

>(findzips 'california)
(90001 900263)

>(findzips 'berlin)
empty

I try to this by code below but it only return first value not a list

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

I'm not allowed to use ! functions or let.

First, there's a typo in the code you posted: find3 should be find.

Let's look at that function with proper indentation:

(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

If the current entry matches, you don't try to look for any subsequent match. So the list you return will never contain more than one element.

You always need to look for subsequent elements, i.e. you always need to call (find x (cdr zipcodes)). A good way would be to call let, but your homework assignment rules that out. You can just duplicate the call. Rather than make a single-element list with the list procedure, build a list consisting of the current match followed by the list of subsequent matches. The procedure to add one element to a list is 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

This isn't finished: you'll notice this function always throws an exception. You grind down the list, eventually reach the end… and choke because you aren't handling the case when the list is empty. I'll leave this as an exercise.

Now there are other ways to write this function (in fact, better ways, but harder to understand for a beginner). They may or may not be what was intended in your assignment. Imagine you only wanted to have a single recursive call to find, and no let or any other way to store the result of calling find. Then you have no choice but to call find, but with different arguments depending on whether the element was found or not. How can you do this? (Hint: you'll need a third argument.)

The first step towards understanding this problem is to state explicitly what the data we're working with consists of. Let's write down a series of data definitions:

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

An ENTRY is a list of a ZIP, a CITY and a STATE. Recall, however, that a list is a series of cons cells ending with null. Let's write our data definition for ENTRY using explicit calls to 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])

With those data definitions in hand it is easier to be precise about what we want our function to do. We'll write down a contract for our function consisting of two parts: the function's name and kind of data the function consumes and the kinds of data the function produces. For example:

;; <FUNCTION NAME> : <WHAT OUR FUNCTION CONSUMES> -> <WHAT OUR FUNCTION PRODUCES>

Now we can write a contract for the functions we want to write:

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

Let's start filling in the definition for find. We know from our contract that 'find' takes two arguments, a STATE and a [listof ENTRY]. We know from the data definition for [listof ENTRY] that it can be one of two things: (cons ENTRY [listof ENTRY]) or null. Any time we have to handle more than one case we can use cond to the behavior we want in each case:

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

Refer to your textbook or ask your instructor if cond is unfamiliar to you.

So far so good. So what should our function return if it is called null (a valid input given our contract)? Our contract suggests that we should return an empty list in return.

;; find : STATE [listof ENTRY] -> [listof ZIP]
(define (find state entries)
  (cond ((null? entries) null)
        (else ...)))

So far so good. Now for the hard part. If the input list is not empty, then it must contain at least one ENTRY. For any given ENTRY we have to handle two cases: Either the state in the entry matches the STATE we're looking for, or it doesn't. Let's imagine that we have a function, get-state that, given an ENTRY, gives us its 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

Let's handle the second case first. In the case where the STATE we're searching for doesn't match the STATE in the next ENTRY in entries we simply want any ZIPs that match in the rest of the list. Looking at the contract for 'find' we can see that calling find on the rest of the list will give us exactly what we want! Filling that in we have:

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

In the first case we know that the first ENTRY in 'entires' has a state that matches the STATE we're searching for. Consider what we want for our final result in this case: We'd like a list beginning with the ZIP that we already know matches the STATE we're searching for followed by any other ZIPs with states that also match in the rest of entries. We can use cons to construct a new list. cons has the following contract:

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

The first argument to cons is simple. Let's assume, again, that we have a function 'get-zip' that gives us the ZIP for a given ENTRY. We could then simply extract the ZIP from the 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))))))

The second argument to cons I'll leave as an exercise to you.

We're nearly finished! Now that we have find writing findzips is trivial. We simply call find with the given STATE and zipcodes as its arguments. Fill in the remaining ellipses and you'll be finished:

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

In solving this problem we made use of elements of the "Design Recipe", a step-by-step guide to designing programs. The "Design Recipe" is outlined in full in "How to Design Programs" by Felleisen, Findler, Flatt and Krishnamurthi. The full text is available online: www.htdp.org.

Good luck!