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
(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?