Does Emacs has a built-in function for unpacking lists with an arbitrary depth that keeps nil values?

Question

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)

Answer 1

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

Answer 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.

Answer 3

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.