Help With Lisp Code for a Binary Tree

Question

I have

(setq l2 '(1 (2 b (c 1 b))(a (1 2) d))) 

(defun drumuri (l3) 
  (cond ((atom l3) (cons l3 nil))
     (t (append
           (cons (car l3) nil)
           (drumuri (cadr l3))
           (cons (car l3) nil)
           (drumuri (caddr l3))))))

(drumuri l2)

and it gives me:

 Break 2 
[4]>     DRUMURI
 Break 2 
[4]>     (1 2 B 2 C 1 C B 1 A 1 2 1 NIL A D)

but i need:

((1 2 B)(1 2 C 1)(1 2 C B)(1 A 1 2)(1 A D)) 

Ok good news i found some of the answers:

(setq l2 '(1 (2 b (c 1 b))(a (1 2) d)))
( defun drumuri (l3) 
( cond ( (atom l3) ( cons l3 nil))
       (t (append  ( cons ( car l3 ) nil)
          (drumuri ( cadr l3) )))))
          (drumuri l2)

and the answer to that is:

[1]> 
(1 (2 B (C 1 B)) (A (1 2) D))
[2]> 
DRUMURI
[3]> 
(1 2 B)

Next is the second answer:

(defun drumuri (l4) 
    (cond ((atom l4)(cons l4 nil))
    ( t   ( append  (cons ( car l4)nil)
        (drumuri ( caddr l4))))))
            (drumuri l2)

and the answer to that is:

[1]> 
(1 (2 B (C 1 B)) (A (1 2) D))
[2]> 
DRUMURI
[3]> 
(1 A D)

So all that is left is to find:

(1 2 C 1) (1 2 C B) (1 A 1 2)

Answer 1

A tricky problem. Not particularly complex, but with some finicky edges. Since this is obviously homework, I'm going to try to help you, but at the same time avoid just spoon-feeding you (and possibly fail at one or both of these goals). So I've written it in Python. Hopefully that's far enough away from Lisp that you'll still have to do a good slab of thinking for yourself.

>>> import operator
>>> def drumuri(a):
...     if isinstance(a, list):
...         return reduce(operator.add,
...                       [[a[:1] + d for d in drumuri(x)] for x in a[1:]])
...     else:
...         return [[a]]
... 
>>> drumuri( [1, [2, 'b', ['c', 1, 'b']], ['a', [1, 2], 'd']] )
[[1, 2, 'b'], [1, 2, 'c', 1], [1, 2, 'c', 'b'], [1, 'a', 1, 2], [1, 'a', 'd']]
>>> 

Here's the key insight lacking from your Lisp version. Because drumuri is recursive, every level must return the same kind of structure to its caller: a list of paths, where each path is a list. In short, drumuri must always return a list of lists. Your leaf case returns a list containing a single atom.

You are also making some mistakes with the use of append, but the leaf issue is probably bending everything else out of shape.

EDIT: Let's see if can help you discover the solution for yourself. Follow these steps:

1. Write a function called prepend-to-paths that takes a single head and a list of paths, and returns a list of paths with the head added to the front of each original path. It should work as follows:

   > (prepend-to-paths 1 '((2 B) (2 C 1) (2 C B) (A 1 2) (A D))) ;'
   ((1 2 B) (1 2 C 1) (1 2 C B) (1 A 1 2) (1 A D))
   

2. Write a function called convert-to-paths that takes a list of unprocessed tail elements and converts them to paths. Rather than doing all the work itself, however, it should only worry about mapping the input to a list of paths (relying on the as-yet unwritten drumuri to map each element) and then concatenating the returned lists of paths into a single list of paths. The output (once drumuri exists) should be like so:

   > (convert-to-paths '((2 b (c 1 b)) (a (1 2) d))) ;'
   ((2 B) (2 C 1) (2 C B) (A 1 2) (A D))
   

3. Write the drumuri function. It should use cond as per your original, but replace the leaf case with an expression that returns the atom as a list of paths:

   > (drumuri 'b) ;'
   ((b))
   

   Then replace the (append ...) with code that uses the functions you wrote in the previous steps to transform the head and tail of the input list input a list of paths.

4. Once the three functions are working together nicely, you could try to figure out how to fold the first two into the body of drumuri. Note that the end-result of this may be structurally different to the Python solution I gave.

If and when you get stuck, just update your question with whatever progress you've made and whatever code you've managed to cobble together.