1

What I'm looking for

I want to have a function that given the following inputs, returns the following outputs.

Input

(1 nil)
(1 (2) (nil))
(1 (2 (3)) (nil (nil)))
(1 (2 (3 (4))) (nil (nil (nil))))
(1 (2 (3 (4 (5)))) (nil (nil (nil (nil)))))

Output

(1 nil)
(1 2 nil)
(1 2 3 nil nil)
(1 2 3 4 nil nil nil)
(1 2 3 4 5 nil nil nil nil)

Background

Some days ago, I asked a question on the same topic, but I hadn't explicitly stated that I wanted to keep nil values, so I'm creating a new question.

This answer to a question that was linked to my question recommended using flatten-tree. This comment recommended using -flatten from the dash.el package. I have used both, but none of them keep nil values. See output of evaluation below.

(let ((cases '((1 nil)
               (1 (2) (nil))
               (1 (2 (3)) (nil (nil)))
               (1 (2 (3 (4))) (nil (nil (nil))))
               (1 (2 (3 (4 (5)))) (nil (nil (nil (nil))))))))
  (cl-loop
   for case in cases
   do (progn
        (princ (format "flatten-tree: %s\n" (flatten-tree case)))
        (princ (format "-flatten: %s\n" (-flatten case))))))
flatten-tree: (1)
-flatten: (1)
flatten-tree: (1 2)
-flatten: (1 2)
flatten-tree: (1 2 3)
-flatten: (1 2 3)
flatten-tree: (1 2 3 4)
-flatten: (1 2 3 4)
flatten-tree: (1 2 3 4 5)
-flatten: (1 2 3 4 5)
5
  • See the comments about this case in C-h f -flatten, although I suspect neither suggestion will be palatable.
    – NickD
    Commented Aug 17, 2023 at 3:36
  • 2
    I can't help but feel that having nil as "meaningful" elements in a list is asking for trouble. It will require constant vigilance to make sure that everything you do maintains the structure and after a while it will be exhausting. I would recommend that you change the data representation. But I can't really point to a fire: I just think that I smell smoke.
    – NickD
    Commented Aug 17, 2023 at 3:47
  • 1
    @NickD Thanks! I see your point and I'll take this into consideration. I will be using a symbol (perhaps, gap or empty) instead of nil to avoid such problems. Commented Aug 17, 2023 at 4:10
  • 1
    It will be difficult for you to distinguish between nil and empty list.
    – shynur
    Commented Aug 17, 2023 at 5:22
  • 1
    emacs.stackexchange.com/tags/elisp/info
    – Drew
    Commented Aug 17, 2023 at 15:40

3 Answers 3

3

This is not a direct answer to your question, because you asked for a built-in solution which I am not aware of.

But in your answer you wondered whether there is a non-recursive solution.

It is clear that we need a stack for the DFS. Recursion exploits the call stack for this. But in an iterative version we can roll our own stack.

The only special thing about the nils you want to keep is that they are stored in cars. We can just identify them and keep them.

(defun flatten-tree (tree)
  "Flatten TREE.
This treats nil-entries in lists like non-lists."
  (let ((stack (list tree))
        list)
    (while stack
      (while (car stack)
        (if (and (listp (caar stack))
                 (caar stack)) ;; non-empty list
            (let ((next-tree (caar stack)))
              (setcar stack (cdar stack))
              (push next-tree stack))
          (push (caar stack) list) ;; (caar stack) can be the empty list
          (setcar stack (cdar stack)))
        )
      (pop stack))
    (nreverse list)))

We are testing the flatten-tree with following form:

(mapcar #'flatten-tree
    '(
      (1 nil)
      (1 (2) (nil))
      (1 (2 (3)) (nil (nil)))
      (1 (2 (3 (4))) (nil (nil (nil))))
      (1 (2 (3 (4 (5)))) (nil (nil (nil (nil)))))))

and get the desired result:

((1 nil)
 (1 2 nil)
 (1 2 3 nil nil)
 (1 2 3 4 nil nil nil)
 (1 2 3 4 5 nil nil nil nil))
1
2

Since nil is the same thing as '() you're asking for trouble by forcing the code to conflate the data and the structure. If you can use a different, more domain-meaningful value than nil, you should use that.

Otherwise, given the unpredictability of the depth of the data and the structure, then you are obligated to do a deep traversal of the data structure and explode it progressively, keeping the special case of a list with 0 elements as something that does not explode but keeps its shape.

So.. Recursion it is.

0

The following function is based on this answer to my previous question.

(defun unpack-list (lst)
 (cond
   ((null lst) '(nil))
   ((atom lst) (list lst))
   (t (apply 'append (mapcar #'unpack-list lst)))))

(unpack-list '(1 (2 (3 (4 (5)))) (nil (nil (nil (nil))))))
(1 2 3 4 5 nil nil nil nil)

I'm wondering if there are more effective solutions than a recursive function.

6
  • 1
    What's wrong with a recursive function?
    – NickD
    Commented Aug 17, 2023 at 3:36
  • (unpack-list '()) --> (nil), so a list of 0 elements becomes a list of one element...
    – NickD
    Commented Aug 17, 2023 at 3:40
  • @NickD As far as I'm concerned, recursive functions use stack frames to maintain the context of recursive calls which require more memory than using a well thought iterative function (unless I'm wrong in which case I'll be more than happy to have learnt something new) Commented Aug 17, 2023 at 3:52
  • 1
    It may or may not: it depends on the function, the compiler and perhaps other details (and admittedly the Emacs Lisp implementation is not optimized for recursive functions), but these things pale into insignificance when you have to read the code. Relatively simple recursive functions become tricky, complicated hairballs when written iteratively. In any case, this is a deep topic that's probably unsuitable for this site.
    – NickD
    Commented Aug 17, 2023 at 4:15
  • Any chance of arbitrary recursion is best avoided in elisp. It depends on your use cases and who it the code is for, though; but if you're aiming for "guaranteed robust for any possible input" then not using recursion eliminates a failure case (and I'd be concerned more about blowing the stack than memory usage, but YMMV). If you have no concerns about inputs of that nature, though, I don't think there's any problem.
    – phils
    Commented Aug 17, 2023 at 4:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.