Why is this function in an infinite loop - learning lisp

Question

(EDIT: I'm not going to worry about TCO yet)

I'm (finally getting around to) learning Lisp. I'm trying to write my own (naive-ish) function to flatten a list. I'm starting with the simpler cases and will build it up to handle more complex cases if it doesn't work. Unfortunately right now, I'm getting an infinite loop and can't quite figure out why.

I also don't know how to use any debugging methods in lisp so if you could point me in that direction, too I'd appreciate it.

(defun flattenizer (lst)
  (if (listp (car lst))
    (flattenizer (car lst))
    (if (null lst)
      nil
      (cons (car lst) (flattenizer (cdr lst))))))

final code:

(defun flattenizer (lst)
  (cond
    ((null lst) nil)
    ( (consp (car lst)) 
        (nconc (flattenizer (car lst)) (flattenizer (cdr lst)) ))
    (T (cons (car lst) (flattenizer (cdr lst))))))

tests:

* (flattenizer '((1 2) (3 4)))

(1 2 3 4)
* (flattenizer '(1 (2 3) (4 5)))

(1 2 3 4 5)
* (flattenizer '((1 2) 3 (4 5) 6))

(1 2 3 4 5 6)
* (flattenizer '(1 2 3 4))

(1 2 3 4)

Answer 1

(listp NIL) returns T, and so does (listp (car NIL)), so when you hit the end-of-list and recurse on NIL, looping happens.

You need to change the order of your tests, testing for the (null lst) first, to avoid the looping. Better re-write it with cond for that. It's easier to change the ordering of tests, with cond.

Then you'll notice that for some reason you only flatten the first element in your argument list, ever. What about (3 4) in ((1 2) (3 4)) etc.? We should really somehow combine the results of flattening the car with the results of flattening the cdr.

If the result of flattening a list is a list, then we will need to combine the two resulting lists. Also, since we will be combining lists, if we encounter an atom we will have to produce a list, as the result of flattening that atom.