Geek Answers Handbook

Why this function in an infinite loop - learning lisp

(EDIT: I will not worry about TCO yet)

I (finally get along) by learning Lisp. I am trying to write my own (naive-ish function) to flatten the list. I start with simpler cases and create it to handle more complex cases if it doesn't work. Unfortunately, now I get an infinite loop and cannot understand why.

I also don't know how to use any debugging methods in lisp, so if you could point me in that direction, I would also 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)
+4
source share
3 answers

(listp NIL) returns T , as well as (listp (car NIL)) , so when you click on the end of the list and recurs to NIL , a loop occurs.

First you need to reorder your tests, first check (null lst) to avoid a loop. Better rewrite it with cond for this. Easier to reorder tests, cond .

Then you will notice that for some reason you are only smoothing the first element in the argument list. What about (3 4) in ((1 2) (3 4)) , etc.? We must somehow combine the results of smoothing car with the results of flattening cdr .

If the result of smoothing the list is a list, then we will need to combine the two resulting lists. In addition, since we will combine lists, if we run into an atom, we will need to create a list as a result of smoothing this atom.

+6
source

NIL somewhat "weird" in Common Lisp for a combination of practical and historical reasons. For instance:

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

In a recursive code call for (car x) , when (listp (car x)) calls infinite recursion, because NIL is a list and its car itself.

+5
source

Debugging using SBCL.

Tell SBCL what you want to 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

Performing 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

It looks like you're in a loop right now.

Returning to the upper level.

 1] top *

Now check the source code.

+4
source

More articles:


All Articles