CODEWITHSUNDEEP
scheme
Mintyique
Mintyique

Reputation: 23

Scheme Programming finding items in nested loops

I have the following items

(define itemslist
  (list 'a1 'b2 'c3 (list 'z1 'z2) 'd5 'e6))

My method to find items is below

(define find-item
  (lambda (item itemslist)
    (cond ((null? itemslist) #f)
          ((list? (car itemslist))
            (cond ((null? itemslist) #f)
                  (else (find-item item (car itemslist)))))
          ((equal? stn (car itemslist)) (display "found"))
          (else (find-stn stn (cdr itemslist)))
          )
    )
  )

With my method above I can find a1, b2, c3, z1, z2. But when I want to find d5 onwards, it returns nothing. It seems to have skip the stack. Btw, I am just starting to learn Scheme so simple explanation would be better.

One more qns, how about if I have this

(list 'a1 'b2 'c3 (list 'z1 (list 'y1 'y2) 'z2) 'd5 'e6)

does this works as well? Thanks!

Upvotes: 2

Views: 599

Answers (3)

Mayer Goldberg
Mayer Goldberg

Reputation: 1438

Even though you got your [specific] answer, here's something that might help you with similar questions. 

(define describe
  (lambda (e)
    (cond #;((list? e)
             `(list ,@(map describe e)))
          ((pair? e)
           `(cons ,(describe (car e))
                  ,(describe (cdr e))))
          ((vector? e)
           `(vector ,@(map describe (vector->list e))))
          ((or (null? e) (symbol? e)) `',e)
          (else e))))

This procedure prints the code that generates a given sexpr. For example:

> (describe '(a 2 b 3))
(cons 'a (cons 2 (cons 'b (cons 3 '()))))

It will also place the quotes where needed, so it places them before symbols or () but not before numbers. When you are comfortable with nested pairs, you may want to remove the #; on the third line, to generate more compact output:

> (describe '(a 2 b 3))
(list 'a 2 'b 3)

This code can teach you many things about quote. For example:

> (describe ''''a)
(list 'quote (list 'quote (list 'quote 'a)))

Upvotes: 0

erjiang
erjiang

Reputation: 45657

To write more for the sake of writing more... This is usually called a "tree-walk" because a nested list like that is really a binary tree. Lists are really made up of binary pairs, so when you have a pair (l . r), l is the left branch of the tree and r is the right branch of the tree.

For example, '(1 (2 3) 4) is short for '(1 . ((2 . (3 . ())) . (4 . ()))) which can be drawn as

     .
    / \
   1   .
      / \
     /   .
    /   / \
   .   4  ()
  / \ 
 2   .
    / \
   3  ()

and at any pair (l . r), car gets you the left tree and cdr gets you the right. So, when you write (pair? ls), you're really asking if you're at a branch in the tree, at which point you should recur on both the left branch (car) and the right branch (cdr). Hope that helps you understand lists.

Upvotes: 2

Nick Dandoulakis
Nick Dandoulakis

Reputation: 43110

Yes, you skip lists.
Example:

'(1 '(2 3) 4)

If (list? '(2 3)) is true, the else part (outer cond) wont be evaluated so 4 is skipped.
So, either you place the else part inside list? block or you redesign your code.

If the itemlist is a list/pair you can pass it right away in a recursive call so
you can avoid writing code like (car itemslist) inside predicates thus make the code simple.

Here is a redesigned (simplified) version:

(define (find-item item l)
  (cond ((equal? item l) #t)
        ((pair? l) (or (find-item item (car l)) (find-item item (cdr l))))
        (else #f)))

Tip: you can also can write lists with '(...) notation instead of (list ...), ie

(find-item 'z2 '('a1 'b2 'c3 '('z1 '('y1 'y2) 'z2) 'd5 'e6))  
#t  
(find-item 'e6 '('a1 'b2 'c3 '('z1 '('y1 'y2) 'z2) 'd5 'e6))  
#t

Upvotes: 4

Related Questions