How to avoid duplicating code in cond clause LISP?

Question

I am supposed to find the path from the root to a given node in LISP. Preferably using a purely functional approach.

The binary tree representation uses sublists, e.g.: (A (B) (C (D) (E))) - A is the root, B the left child of A, C the right child of A, D the left child of C and E the right child of C.

It seems to me that there should be some way to avoid the duplication of the following function calls:

(get-path (cadr l) x)

(get-path (caddr l) x)

I am new to LISP and I don't know and can't seem to find a solution for this, but I think there must be a -purely- functional way to do it. Maybe using lambdas? Not sure how, though. Am I using a wrong approach? Any kind of help is highly appreciated.

;;; l is the list with the binary tree
;;; x is the node we are looking for
(defun get-path(l x) 
    (cond
            ;; nothing to search for anymore
            ((null l) nil)
            ;; found the node we were looking for
            ;; in this case we return a list containing only x
            ((equal (car l) x) (list x))
            ;; the node was found on the left branch
            ((not(equal (get-path (cadr l) x) nil))
                     (cons (car l) (get-path (cadr l) x)))
            ;; the node was found on the right branch
            ((not(equal (get-path (caddr l) x) nil))
                     (cons (car l) (get-path (caddr l) x))))) 

Answer 1

What you can do is replicate the anaphoric conda and ifa macros from TXR Lisp in Common Lisp. (Source code here; good luck!)enter link description here

Then you can write it like this, referring to the get-path expressions using the anaphoric it variable.

(conda
  ;; nothing to search for anymore
  ((null l) nil)
  ;; found the node we were looking for
  ;; in this case we return a list containing only x
  ((equal (car l) x) (list x))
  ;; the node was found on the left branch
  ((not (equal (get-path (cadr l) x) nil)) (cons (car l) it))
  ;; the node was found on the right branch
  ((not (equal (get-path (caddr l) x) nil)) (cons (car l) it)))

conda is clever about expressions of the form (not x) and (null x) (also (false x) in TXR Lisp). If the test expression is one of these, then it recurses into the x do ferret out the "anaphoric it".

Note that it binds to places not just to values. Not only is the target of it not evaluated more than once, if the target is a place, then it refers to that place:

(ifa (< x 10)
  (inc it)) ;; increments x.

This aspect of ifa is achieved with the help of the placelet macro, which doesn't exist in Common Lisp. A quick and dirty substitute would be to use symbol-macrolet. The only problem is that that a symbol macro denoting a place allows multiple evaluation of the place whereas placelet evaluates a place once. The resulting lexical symbol then denotes the storage location, rather than the overall expression.

ifa was designed to either wipe the floor with Paul Graham's aif, or else to complement it; conda is trivially based on ifa.

By the way, do not write expressions like

(not (equal whatever nil))

in Lisp! Firstly, equal equality is not particularly meaningful if you are comparing with nil; only nil is equal to nil, and that is according to eq equality, so you might as well have:

(not (eq whatever nil))

Secondly, for something not to be eq to nil means that the something is true. That is to say:

(if (not (eq foo nil)) do-this)   ---same-as--> (if foo do-this)

!

If we refactor your code to get rid of this stuff, then it's better if we have the Paul Graham Style anaphoric if aif (and an acond based on it). That is to say:

(ifa (not (equal (get-path whatever) nil))) (list it))

becomes:

(aif (get-path whatever) (list it))

where the it trivially to the value of the entire test expression, rather than a somewhat cleverly selected constituent of that expression.

Under ifa, this is expressed slightly more verbosely using:

(ifa (true (get-path whatever)) (list it))

Where true can be defined as

(defun true (x) (identity x)).

Without this extra wrapping, ifa will bind it to whatever.

Answer 2

What about this?

(defun root-path (tree element)
  (when tree
    (cons (first tree)
          (unless (eql (first tree) element)
            (or (root-path (second tree) element)
                (root-path (third tree) element)
                (return-from root-path nil))))))

You should even define meaningfully named functions, like tree-value left-subtree and right-subtree, but this is maybe overkill here.

In the above, note that when (resp. unless) is used for its nil value when the condition fails (resp. succeed). You can translate with cond or if expressions if you prefer. The only repetition here is the double (first tree) value, which might be optimized away by the compiler or manually with a surrounding let binding.

Edit

The original code was not working. The solution is to use Joshua's answer, but I won't copy paste it here, so I added the return-from expression. While it works, your teacher and/or coworker will probably not like this approach ;-)

Tests

(mapcar (lambda (n) (root-path '(A (B) (C (D) (E))) n))
        '(a b c d e f))

=> ((a) (a b) (a c) (a c d) (a c e) nil)

Answer 3

I'd combine the final two cond clauses. You want to check the left side and see if there's a path there, and if there is, take it, and if there's not, check the right side. Then, whichever one of those yielded a path (if either did), you want to append to that. That could look like this. First, a couple of functions for convenience:

(defun element (tree)
  (first tree))

(defun left (tree)
  (second tree))

(defun right (tree)
  (third tree))

Now, the real meat of the solution:

(defun get-path (element tree)
  (cond
    ;;  A null tree is empty and doesn't match anything.
    ((null tree) '())
    ;; If the element of this tree is the element, then we have a
    ;; partial path of length 1: (ELEMENT).
    ((eql element (element tree)) (list element))
    ;; Othweise, let PATH be the path on the left or the path on the
    ;; right, whichever exists.
    (t (let ((path (or (get-path element (left tree))
                       (get-path element (right tree)))))
         ;; If there's no path on either side, then return NIL.
         ;; Otherwise, prepend the current element onto the path that
         ;; exists.
         (if (null path) '()
             (list* (element tree) path))))))

Note that list* does the same thing as cons, but it makes it clearer that you're working with lists, not just cons cells. You could use cons just as well.

We can confirm that this works as expected:

(defparameter *tree* '(A (B) (C (D) (E))))

(get-path 'c *tree*) ;;=> (A C)
(get-path 'd *tree*) ;;=> (A C D)
(get-path 'f *tree*) ;;=> NIL

Answer 4

Use labels for interior (local) functions:

(defun get-path(l x)
    (labels ((prepend-path (elt)
                (cons (car l) (get-path elt x))))
        (cond
            ;; nothing to search for anymore
            ((null l) nil)
            ;; found the node we were looking for
            ;; in this case we return a list containing only x
            ((equal (car l) x) (list x))
            ;; the node was found on the left branch
            ((not(equal (get-path (cadr l) x) nil))
                     (prepend-path (cadr l)))
            ;; the node was found on the right branch
            ((not(equal (get-path (caddr l) x) nil))
                     (prepend-path (caddr l))))))

Alternatively, you could use flet instead of labels because you don't have interior functions that refer to each other. Personally, I use labels and hardly ever use flet for that reason (plus the overhead of re-indenting the function.)