Как сравнить два списка в lisp, которые не совпадают по длине или структуре? - PullRequest
Новая
       21

Как сравнить два списка в lisp, которые не совпадают по длине или структуре?

0 голосов
/ 06 марта 2012

У меня есть два списка: 

'(and 1 (or a b))
'( (a 0)(b 1) )

Я новичок в lisp, и мне очень трудно понять, как сравнить эти два списка.Я думаю о создании функции сравнения, но я не знаю, как сравнивать их одно за другим, поскольку в lisp значения не возвращаются, пока выражение не будет оценено.Поскольку они тоже не одинаковы, я не могу предположить, что они будут одинаковыми, по крайней мере, структурно.Любое объяснение, как это работает?

Редактировать: Извините, я забыл сказать, почему я сравниваю.Во втором списке предполагается связать число с тем местом, где эти переменные существуют в первом списке.Таким образом, результирующий первый список должен быть: 

'(and 1(or 0 1))

Ответы [ 2 ]

3 голосов
/ 06 марта 2012

Встроенный: 

$ clisp -q
[1]> (sublis '((a . 0) (b . 1)) '(and 1 (or a b)))
(AND 1 (OR 0 1))
[2]>

Таким образом, домашняя работа сводится к созданию оболочки для SUBLIS, которая принимает привязки в форме ((a 0) (b 1)), а не ((a. 0) (b. 1)).

Clue: 

(loop for (x y) in vars collecting (cons x y))
0 голосов
/ 06 марта 2012 
;;; Look up a var like A a list like ((A 0) (B 1))
;;; and retrieve the (A 0). Or nil if not found.
(defun lookup-var (var bindings)
  (find var bindings :key #'first))

;;; The homework
(defun subst-vars (tree bindings)
  (cond
    ;; if the tree is a cons cell, then substitute in the
    ;; car, substitute in the cdr, and combine the results by consing
    ;; a new cons! Easy!
    ((consp tree) (cons (subst-vars (car tree) bindings)
                        (subst-vars (cdr tree) bindings)))
    ;; Otherwise the tree must be an atom. See if the atom is
    ;; a var that we can substitute. If not, return the atom.
    (t (let ((binding (lookup-var tree bindings)))
         (if binding
           (second binding) ;; got a binding entry; return its value!
           tree)))))            ;; no deal, just return the original

Напечатал это прямо в окне stackoverflow, и оно запустилось без изменений. :)

Это довольно неэффективно, хотя. Предположим, что переменные вообще не встречаются в дереве. Это делает расточительную копию дерева, а не просто возвращает дерево. Чтобы вы поработали над этим самостоятельно, можете ли вы найти способ оптимизировать его, чтобы избежать ненужного вызова функции cons? Подсказка: проверьте, возвращают ли рекурсивные вызовы subst-переменных один и тот же объект.

...