Problems with recursion trying to learn Scheme

2019-09-13 22:18发布

问题:

I have created a function that will insert a list into a defined emtpy list. The list that I am inserting will have some type of keyword for finding it (for example maybe a name or a location) followed by a nested list that will contain some sort of information such as an age of a call record or something (again this is just me trying to learn the recursive syntax). My problem lies in how do I

  • traverse through the bigger list and

  • let the program know that there are several lists within a bigger list and how to differentiate between them.

For example, if I use my function to add a list that is '(John (AL 25 40 67) (CA 40 67 24)) to an empty list, and then I add another similar list under a different name such as '(Sue (AZ 45 6 78)), how do I tell it that these are essentially two different records stored under a name.

My first thought process was to traverse the list until it finds the name and then from there cdr and car in order to get to whatever info I needed to pull; but if I start to cdr and car wouldn't it eventually go past that name's record?

(define (db_insert rec)
  (set! db (cons rec db))
  (display db)  

  (display "\n There is/are ")
  (display (count))
  (display " record(s) in the database"))

This is my code to insert a list

(define getName name)
  [(empty? db) '()]
  [(equal? (car(car db)) name) (car db)]

this would return if it is equal... Do I assume correctly? But how do I keep traversing?

EDIT Okay, This is my current problem. So again my lists or "records" that are appended together into an empty list are in the format (Matthew (AL 21 32)). I am now trying to write a function that would use the getName (I renamed it fetchRecord) in order to find the desired record and then multiply the two numbers inside the record. However, my current code works only if I am getting the name on the first record but it returns an empty list for any record after that. Here is my code:

(define (Bill_Amt name)
  (cond
    [(empty? db) #f]
    [else
      (* (car(cdr(car(cdr (fetchRecord name)))))
         (car(cdr(cdr(car(cdr (fetchRecord name)))))))]))

How would I fix this? Also if a certain record has two sets of data like so: '(John (AL 25 40) (CA 40 67)) then how would you go about getting it to output both 25*40 and 40*67 etc., and even if it has more than two sets of data? I understand that it would be recursion but am not quite sure how you would set it up since the usage of car and cdr would change.

回答1:

You are trying to create and manipulate a dictionary. In Lisp, when implemented on lists, it is known as assoc-list, for each entry can be gotten to by means of the built-in function assoc.

Perhaps you intend to re-implement it, as part of your learning experience.

First, since you tag your entries with different names, when you hit the name you search for, you've found it. Presumably, you wouldn't tag different entries with the same name. When you have exhausted your list, i.e. gotten to the stage where it is '(), then you know that your search has ended, and you haven't found what you were searching for.

To traverse the list, you just use car, to inspect its first entry, and cdr to get rid of it.

When you get hold of an entry, you can inspect its first element, the name, again by using car.

When writing functions, pay attention to not use any names out of the blue -- use what arguments your function was supplied with. And of course pay attention to parentheses.

(define (get-name name db)
  (cond
    [(empty? db)                     ; end of list reached --
          #f]                        ;   use #f to signal failure
    [(equal? (car (car db)) name)    ; found entry with same name --
          (car db)]                  ;   return it
    [else (.... name (cdr db))]))    ; else go on working on the rest of the list

See also: cond.

As for db-insert, follow the same code outline as for traversal, and return the updated assoc-list.

(define (db-insert name data db)
  (cond
    [(empty? db)                          ; end of the list
         (list   (cons name .... ))]      ; new entry, name wasn't found
    [(equal? (car (car db)) name)         ; same name found --
         (cons   ....                     ; an updated entry goes here
                 (cdr db))]
    [else                                 ; mismatch -- 
         (cons (car db)                   ;      preserve the current entry, and
               (db-insert name data       ;      go on working
                          (......)))]))   ;      on the rest of the list