CODEWITHSUNDEEP
recursionlispinfinite-loop
Ramy
Ramy

Reputation: 21261

Why is this function in an infinite loop - learning lisp

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

Upvotes: 4

Views: 432

Answers (3)

6502
6502

Reputation: 114609

NIL is somewhat "strange" in Common Lisp for a mix of practical and historical reasons. For example:

  • NIL is a symbol: (symbolp NIL) ==> T
  • NIL is a list: (listp NIL) ==> T
  • NIL is not a cons cell: (consp NIL) ==> NIL
  • but you can take car/cdr of it anyway: (car NIL) ==> NIL and (cdr NIL) ==> NIL

In your code calling recursively for (car x) when (listp (car x)) is causing infinite recursion because NIL is a list and its car is itself.

Upvotes: 5

Will Ness
Will Ness

Reputation: 71119

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

Upvotes: 6

Rainer Joswig
Rainer Joswig

Reputation: 139411

Debugging using SBCL.

Tell SBCL you want debug:

* (proclaim '(optimize (debug 3)))

Your code:

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

FLATTENIZER

Stepping it with STEP

* (step (flattenizer '(1 (2 3) 4)))
; Evaluating call:
;   (FLATTENIZER '(1 (2 3) 4))
; With arguments:
;   (1 (2 3) 4)

next step

1] step
; Evaluating call:
;   (FLATTENIZER (CDR LST))
; With arguments:
;   ((2 3) 4)

next step

1] step
; Evaluating call:
;   (FLATTENIZER (CAR LST))
; With arguments:
;   (2 3)

next step

1] step
; Evaluating call:
;   (FLATTENIZER (CDR LST))
; With arguments:
;   (3)

next step

1] step
; Evaluating call:
;   (FLATTENIZER (CDR LST))
; With arguments:
;   NIL

next step

1] step
; Evaluating call:
;   (FLATTENIZER (CAR LST))
; With arguments:
;   NIL

next step

1] step
; Evaluating call:
;   (FLATTENIZER (CAR LST))
; With arguments:
;   NIL

Looks like you are in a loop now.

Getting back to the toplevel.

1] top

*

Now check your source code.

Upvotes: 4

Related Questions