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.

The call to length is not a good idea, since it will traverse the whole list. APPEND returns a list. You are not using it. That's also not a good idea. sub-tree and sub-sub-list are undefined variables. Also not good. — Rainer Joswig
– Rainer Joswig, Commented Feb 27, 2019 at 20:33
Can you describe what the algorithm you are trying to implement is intended to do (not just by a single case). — user5920214
– user5920214, Commented Feb 27, 2019 at 20:51

coredump · Accepted Answer · 2019-02-28 08:35:43Z

4

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

edited Feb 28, 2019 at 8:35

answered Feb 27, 2019 at 22:26

coredump

39.4k7 gold badges47 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

trickster Over a year ago

Did something similar to this after googling a lot. Can you tell me why did you use list* instead of list.

coredump Over a year ago

@trickster For example, (list* 1 2 '(3 4 5)) produces the list (1 2 3 4 5); the last element is a list; for comparison, with list, all parameters are expected to be elements, so the result would be (1 2 (3 4 5)). In the particular case where we only prepend one element in front of the list, this could be replaced by (cons i ...). I did it like so to match the expected output.

user5920214 · Accepted Answer · 2019-02-27 22:37:31Z

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

Thank you. I have very limited knowledge of Lisp. I only know a handful of macros (not even sure what exactly lisp macros are) and like you have guessed I have coded in python before (but I mostly code in JS) and I like a lot of indentation. Again thanks for taking the pain to explain in detail so much. I didn't mention the entire algorithm as my problem is quite evolved and I am trying to do it in chunks.
@trickster doing stuff in chunks is a very good approach, but then, do explain what your chunk is supposed to be doing.

Collectives™ on Stack Overflow

Build list in Lisp using an iterative recursive function

2 Answers 2

Code style

Alternative

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Code style

Alternative

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related