Программирование схем поиска элементов во вложенных циклах

Question

У меня есть следующие предметы

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

Мой метод поиска предметов ниже

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

Используя мой метод выше, я могу найти a1, b2, c3, z1, z2. Но когда я хочу найти d5 и дальше, он ничего не возвращает. Кажется, нужно пропустить стек. Кстати, я только начинаю изучать Схему, так что простое объяснение будет лучше.

Еще один qns, как насчет того, если у меня есть это

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

это тоже работает? Спасибо!

Answer 1

Да, вы пропускаете списки.
Пример:

'(1 '(2 3) 4)

Если (list? '(2 3)) истинно, то часть else (внешняя cond) не будет оцениваться, поэтому 4 пропускается.
Таким образом, либо вы помещаете деталь else внутри блока list?, либо вы перепроектируете свой код.

Если itemlist является list/pair, вы можете передать его сразу в рекурсивном вызове, поэтому
Вы можете избежать написания кода типа (car itemslist) внутри предикатов, что делает код простым.

Вот переработанная (упрощенная) версия:

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

Совет: вы также можете писать списки с пометкой '(...) вместо (list ...), то есть

(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

Чтобы писать больше ради того, чтобы писать больше… Обычно это называется «обход дерева», потому что подобный вложенный список действительно является двоичным деревом. Списки действительно состоят из двоичных пар, поэтому, когда у вас есть пара (l . r), l - это левая ветвь дерева, а r - это правая ветвь дерева.

Например, '(1 (2 3) 4) - это сокращение от '(1 . ((2 . (3 . ())) . (4 . ()))), которое можно нарисовать как

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

и в любой паре (l . r), car дает вам левое дерево, а cdr дает вам правильное. Итак, когда вы пишете (pair? ls), вы действительно спрашиваете, находитесь ли вы в ветке дерева, и в этот момент вы должны повторить как левую (car), так и правую (cdr) , Надеюсь, это поможет вам понять списки.

Answer 3

Даже если вы получили [конкретный] ответ, вот кое-что, что может помочь вам с подобными вопросами.

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

Эта процедура печатает код, который генерирует данный sexpr. Например:

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

Он также будет помещать кавычки, где это необходимо, поэтому он помещает их перед символами или (), но не перед цифрами. Если вам удобно использовать вложенные пары, вы можете удалить #; в третьей строке, чтобы получить более компактный вывод:

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

Этот код может научить вас многим вещам о цитате. Например:

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