Scheme Programming finding items in nested loops

Question

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!

Answer 1

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

Answer 2

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.