elispon-lisp

Tail-recursive flatten function in Emacs Lisp


I'm going through Paul Graham's On Lisp, and trying to implement the functions in Emacs Lisp. One of them is flatten :

(flatten '(a (b c) ((d e) f)))
;; Returns:
(a b c d e f)

Yet for some reason, the implementation given by Paul Graham does not work on Emacs Lisp (always returns nil):

(defun flatten (x)
  (cl-labels ((rec (x acc))
              (cond ((null x) acc)
                    ((atom x) (cons x acc))
                    (t (rec (car x) (rec (cdr x) acc)))))
             (rec x nil)))

(flatten '(1 (3)))
;; Returns:
nil

Does it have something to do with ELisp's dynamic binding? What's wrong with this code?


Solution

  • As noted in my comment to the question, the problem is a misplaced parenthesis. The definition should be:

    (defun flatten (x)
      (cl-labels ((rec (x acc)
                       (cond ((null x) acc)
                             ((atom x) (cons x acc))
                             (t (rec (car x) (rec (cdr x) acc))))))
        (rec x nil)))
    

    In the original, ((rec (x acc)) defines rec as a function returning nil. By changing it to ((rec (x acc) the cond expression becomes the body of rec, and then after balancing the parentheses again by adding a closing parenthesis after the t clause of the cond, the flatten function works as expected:

    (flatten '(1 (3)))
    (1 3)