I was reading the book On Lisp by Paul Graham. In Chapter 4, Utility Functions, he gives examples of small functions that operate on lists, which would be helpful while writing a larger program.
One of them is flatten. Given a nested list at any arbitrary level as argument, flatten will remove all the nested elements and put them on the top level.
Below is my attempt at implementing flatten:
(defun flatten (lst)
(labels ((rflatten (lst1 acc)
(dolist (el lst1)
(if (listp el)
(rflatten el acc)
(push el acc)))
acc))
(reverse (rflatten lst nil))))
But the above function does not flatten lists properly.
; returns (1) instead of (1 2)
(print (flatten '(1 (2))))
(1)
Calling the function with (1 (2)) returns (1) instead of (1 2).
I cannot find what's wrong with my implementation of flatten. Is it the way I am using
labels? Or is it the the way I am using the dolist macro? The dolist macro always returns nil. But that should not matter as I am using an accumulator acc to store the flattened list.
push changes the symbol binding in scope. Thus the recursion (rflatten el acc) has it's own acc which is the result there but you don't do anything with the returned result and it doesn't alter the callee acc.
Perhaps a (setf acc (rflatten el acc)) would fix that:
(defun flatten (lst)
(labels ((rflatten (lst1 acc)
(dolist (el lst1)
(if (listp el)
(setf acc (rflatten el acc))
(push el acc)))
acc))
(reverse (rflatten lst nil))))