Build list in Lisp using an iterative recursive function

Question

Super newbie in Lisp but at least I am trying so forgive me if the approach seems a bit strange.
I am open to learn new ideas but I will definitely need to learn whats wrong with my approach.
I have a function that builds a list using an iterative recursive approach.

(defun create-tree-iteratively(sub-list)
    (if (equal (length sub-list) 1)
        sub-list
        (loop for i in sub-list
            do(setq subtree (list i))
            do(setq sub-sub-list (remove i sub-list))
            do(append subtree (create-tree-iteratively sub-sub-list))
        )
    )
)

Input to my program is

'(1 2 3)

Expected output is

'((1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1)))

My loops (recursion) runs file. I have issues in combing the output of recursion appropriately.

Answer 1

Code style

• It is preferable to not have closing parentheses on their own lines, the usual convention in Lisp is to have parentheses grouped at the end, like so: ))).

• Since cons-cells have only two slots, CAR and CDR, when they are used as a list they do not hold the length of the list. So the only way to compute the length is to traverse the whole chain of cells, which is exactly what your function is already doing. If your list is of size N, you'll have to compute the length N times, which makes the number of steps in your function proportional to N*N.

• In a loop, a single DO can be followed by multiple expressions, you do not need to repeat the DO keyword. Also, add spaces before opening parentheses.

• SETQ is not supposed to be applied with unbound variables, like subtree or sub-sub-list. You should first have a surrounding let where you introduce local variables (e.g. around the loop), or use with clauses in your loop. Or better, use the existing facilities of LOOP to avoid doing the mutation yourself.

• The return value of APPEND is important, since it 's the results of appending the arguments (which are left unmodified). But here you do not use the return value, which makes the whole expression useless.

Alternative

Instead of computing the length, it is sufficient to check whether the input lists is empty, contains one elements or more (without counting). Also, you can use collect to collect all trees as a list. I am not sure the result for a singleton input list is correct, maybe it should be (list list).

(defun create-tree (list)
  (if (null (rest list))
      ;; covers both empty list and list with a single element
      list
      ;; otherwise, collect a list of trees
      (loop
        for i in list
        ;; collect all trees rooted at i, where a tree is a list (r c1 .. cn)
        ;; with R the root node and C1...CN each child tree. The child trees
        ;; are build recursively, with i removed from the list of values.
        collect (list* i (create-tree (remove i list))))))

Answer 2

Some initial notes.

• When asking a question which involves implementing an algorithm describe the algorithm: it is not easy to guess what you want based on a single example (below I have made two guesses).
• I would guess you have written in Python previously, as your code shows significant signs of 'Python braindamage' (note this is a comment about Python, which I've spent years of my life on, not about your ability). In particular:
  • Lisp does not confuse forms which create new bindings (variables) with assignment the way Python does. You don't create a new binding in a function by setq you create it by some binding form such as let;
  • You don't add new things to the end of a list by append, you create a new list which has the new things added to it, and since lists are linked lists and not variable-length arrays in drag, append takes time proportional to the length of the list.
• But in one respect your code ignores an important lesson of Python: all those group-closing markers don't matter to anyone reading the code, and you should not fill lines with single group closing (or opening) markers. They are just noise which makes reading code hard. In Python, in fact, they are so invisible they don't exist at all. This is one of the things Python got right.

That being said, here are three versions of what I think you want: the first implements what I'd think of as a consistent algorithm, the second implements what I think you may want, and the final one abstracts out the termination test & can do either (or anything else)).

(defun make-permuted-tree (l)
  ;; this builds the tree all the way down
  (if (null l)
      '()
    (loop for e in l
          collect (cons e (make-permuted-tree (remove e l))))))

(defun make-permuted-tree/strange (l)
  ;; this stops before the end
  (if (null (rest l))
      l
    (loop for e in l
          collect (cons e (make-permuted-tree/strange (remove e l))))))

(defun make-permuted-tree/general (l &key (base-test (lambda (b)
                                                       (null b))))
  ;; this stops where you want it to, which by default is at the end
  (labels ((make-permuted-tree (lt)
             (if (funcall base-test lt)
                 lt
               (loop for e in lt
                     collect (cons e (make-permuted-tree (remove e lt)))))))
    (make-permuted-tree l)))

As examples of these:

> (make-permuted-tree/strange '(1 2 3))
((1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1)))

> (make-permuted-tree '(1 2 3))
((1 (2 (3)) (3 (2))) (2 (1 (3)) (3 (1))) (3 (1 (2)) (2 (1))))

> (make-permuted-tree/general '(1 2 3))
((1 (2 (3)) (3 (2))) (2 (1 (3)) (3 (1))) (3 (1 (2)) (2 (1))))

> (make-permuted-tree/general '(1 2 3) :base-test (lambda (b)
                                                    (null (rest b))))
((1 (2 3) (3 2)) (2 (1 3) (3 1)) (3 (1 2) (2 1)))