CODEWITHSUNDEEP
loopslispcommon-lisp
Andy
Andy

Reputation: 10830

How to compare two lists in lisp that are not exactly the same in length or structure?

I have these two lists:

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

I am new to lisp, and I am finding it very hard to figure out how to compare these two lists. I am thinking of creating a comparison function, but I don't know how to compare them one by one as in lisp values aren't returned until the expression is evaluated. Since they aren't the same structure either, I can't assume they will be the same, structurally at least. Any explanation how this works?

Edit: Sorry, I forgot to say why I am comparing. The second list is to suppose to bind the number to everywhere where those variables exists in the first list. So the resulting first list should be:

'(and 1(or 0 1))

Upvotes: 0

Views: 1447

Answers (2)

Kaz
Kaz

Reputation: 58578

;;; 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

Typed this right in the stackoverflow window and it ran with no edits. :)

This is quite inefficient though. Suppose that the variables do not occur in the tree at all. It makes a wasteful copy of the tree instead of just returning the tree. So that you do some work on this yourself, can you figure out a way to optimize it so that it avoids calling the cons function unnecessarily? Hint: check if the recursive calls to subst-vars just return the same object.

Upvotes: 0

Kaz
Kaz

Reputation: 58578

Built in:

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

So the homework reduces to making a wrapper for SUBLIS which accepts the bindings in the form ((a 0) (b 1)) rather than ((a . 0) (b . 1)).

Clue:

(loop for (x y) in vars collecting (cons x y))

Upvotes: 3

Related Questions