Flattening a List containing Empty Lists

Question

As part of a text buffer implemented as a piece table, there is an often called procedure to flatten a nested list of character lists. The function is part of constructing substrings of the buffer for display, copying, and cutting.

I have been using a procedure based on Dan D.'s StackOverflow answer here: https://stackoverflow.com/a/33338608/193509. It has worked admirably except for one corner case.

If the user deletes all of the text in the buffer, the list of characters presented to the flatten function consists of a single element list. The single element is the empty list '().

The "stock" version of flatten does not handle this correctly. I've added a special case to the cond that recognizes the condition and responds appropriately (to my mind any way.) So,

(flatten '(())) ;=> '()

Here's what I have for flatten.

(define (flatten lst)
  (letrec ((helper (lambda (lst acc stk)
                     (cond ((null? lst)
                            (if (null? stk) (reverse acc)
                                (helper (car stk) acc (cdr stk))))
                           
                           ((pair? (car lst))
                            (helper (car lst) acc (if (null? (cdr lst))
                                                      stk
                                                      (cons (cdr lst) stk))))
                           ;; Special case for a list containing just empty lists.
                           ((null? (car lst)) '())
                           
                           (else
                            (helper (cdr lst) (cons (car lst) acc) stk))))))
    (helper  lst '() '())))

But the special case feels clunky and not very general. Is there a better way to do this?

More generally, what should a flattened list containing empty lists look like? I have just assumed that reducing to a single empty list is correct. Likewise, it seems to me that flattening a list containing a mixture of empty lists and non-empty should just return a list of the non-empty elements.

(flatten '(() () ())) ;=> '()
(flatten '((a) (b (x y) c) () (d) () ())) ;=> (a b x y c d)

Any thoughts on that?

Answer 1

In general flatten is intended to flat a tree, not a list, that is to collect all the non-null leaves of the tree in the same order as a classical traversal of the tree. See for instance the definition of flatten in the Racket Manual:

Flattens an arbitrary S-expression structure of pairs into a list. More precisely, v is treated as a binary tree where pairs are interior nodes, and the resulting list contains all of the non-null leaves of the tree in the same order as an inorder traversal.

With this characterization of the function, we do not see empty lists as something that must be “removed” from a list, and here is a simple definition that follows this idea:

(define (flatten tree)
  (let ((lst '()))
    (define (traverse subtree)
      (cond ((empty? subtree) '())
            ((cons? subtree)
               (traverse (car subtree))
               (traverse (cdr subtree)))
            (else (set! lst (cons subtree lst)))))
    (traverse tree)
    (reverse lst)))

The function visits the tree in the classical inorder traversal, and collects all the non-null leaves every time it finds one of them.

From this you can define a more optimized version, if you need to.

Answer 2

So, I started looking at it in a different way, filtering out all '() before flattening. Then I found this answer by Óscar López, which is almost exactly what I needed.

Here's what finally worked:

;; Filter a (possibly nested) list returning a flattened version of the
;; list with only those elements that satisfy the predicate function.
(define (deep-filter pred lst)
  (cond
   ((null? lst) '())
   ((and (atom? lst) (pred lst)) (list lst))
   ((atom? lst) '())
   (else (append (deep-filter pred (car lst))
                 (deep-filter pred (cdr lst))))))

;; Return a flattened list from which all '() have been filtered.
(define (filtering-flatten lst)
  (let ((pred (lambda (x) (not (null? x)))))
    (deep-filter pred lst)))