CODEWITHSUNDEEP
listrecursionprintinglisp
vivek
vivek

Reputation: 13

Just trying to recursively print a list, nothing prints though

I would like to go through a list (which may have nested lists) and have it evaluate to one flattened list with all of the elements. I can't even get a recursive function to evaluate to anything other than nil

(defun pl(lst)
  (if (atom lst)
      lst
    (progn
      (pl (car lst))
      (pl (cdr lst)))))

I'll then call with something like (pl '(1 (2 3) (4 5))), but it always evaluates to nil.

I changed 

(if (atom lst) lst

to

(if (atom lst) (print lst)

and this doesn't even print any of the items of the list.

what concept I am missing here?

Upvotes: 1

Views: 487

Answers (2)

clartaq
clartaq

Reputation: 5372

You might consider looking at an introductory text like "The Little Schemer". One of the first things it does is shows you how to take a consistent approach to problems just like this. The resulting function might look like:

(define (pl lst)
  (cond ((null? lst) '())
        ((not (pair? lst)) (list lst))
        (else (append (pl (car lst))
                      (pl (cdr lst))))))

Sure, this is Scheme, but the approach is the same for Lisp:

  • Check for the special case where the argument is nil
  • Check for the special case where the argument is an atom
  • Recursively apply the function to the car and cdr of the argument, appending the results

The same function in Lisp would look like:

(defun pl (lst)
   (cond ((null lst) '())
         ((atom lst) (list lst))
         (t (append (pl (car lst))
                    (pl (cdr lst))))))

Arguments can be made that this is not the most efficient code, but that isn't the point. This type of pattern occurs over and over again. It's a good idiom to learn.

Upvotes: 1

Beef
Beef

Reputation: 891

A function will normally only return one value, which is value of its body. If you look closely at pl you see that it is an if form, so pl either returns the value of lst or the value of progn.

The first thing I have to point out here is that the return value of a (progn ...) form is the value of its last expression, which in this case is the recursive call (pl (cdr lst)). As you do not do anything with the return value of (pl (car lst)) this call has no effect whatsoever. The value of the recursive call will at some point fall through the atom test. The second thing to point out here is that (atom nil) is also true. Remember that the last element of a list is nil, so when you give pl a list it will always return nil as you have observed.

If your print version shows nothing, it is probably because the print output is shown somewhere else, in another buffer for example.

As for the solution: you either want a pure recursive solution by using append instead of progn, because that's what in your homework assignment. In regular lisp you just use one of the iteration constructs.

My advice is to check any textbook on lisp or scheme to grasp the fundamentals of recursion and tail-recursion.

Upvotes: 4

Related Questions