The Nerdiest Place on Earth

Although I’m no stranger to recursion, it took me a little bit to figure out how to do it in Lisp. Today I decided to see if I could write up a simple example.

I set my sights low for the goal: I want to take a list and print the whole thing, then all but the first item, then all but the first two items, and so on until there’s only one item left. For example, if I had the list (1 2 3 4), the output would look like this:

(1 2 3 4)
(2 3 4)
(3 4)
(4)

With all recursive functions, you need a base case, and the base case here would be that the length of the list is one. The LENGTH function is good for that:

CL-USER> (length (list 1 2 3 4))
4
CL-USER> (length (list 1))
1

That tells us the length of a list, but we aren’t really interested in the length of our list. We don’t need to be that specific. We just want to know whether the list is longer than 1 or not. We can get that with a simple call to the > function:

CL-USER> (> (length (list 1 2 3 4)) 1)
T
CL-USER> (> (length (list 1)) 1)
NIL

To make than easier to grab a hold of, let’s define a function:

CL-USER> (defun longer-than-1 (list)
           (if (> (length list) 1) t))
LONGER-THAN-1
CL-USER> (longer-than-1 (list 1 2 3 4))
T
CL-USER> (longer-than-1 (list 1))
NIL

Now that we have that taken care of, let’s turn our attention to the task of printing the list. To print text, you can use FORMAT like this:

CL-USER> (format t "hello, world")
hello, world
NIL

The same doesn’t quite work for lists, though. If you try to do (format t (list 1 2 3 4)), you’ll get an error. You need the flag ~s, which stands for s-expression, in order to do that:

CL-USER> (format t "~s" (list 1 2 3 4))
(1 2 3 4)
NIL

Now that we have printing and length-figuring-out under control, writing the function that prints a shrinking version of the list isn’t too hard:

(defun show-list (list)
  (format t "~s" list)
  (if (eql (longer-than-1 list) t)
      (show-list (rest list))
      nil))

The first line should look familiar; that’s where we print the list. The rest of the function is just one more function call to IF. If the list is longer than 1, show the rest of the list. Otherwise don’t do anything. Let’s see how it runs:

CL-USER> (show-list (list 1 2 3 4))
(1 2 3 4)(2 3 4)(3 4)(4)
NIL

Pretty good, except it might be nice if there were a newline between each list. We can do that with a ~n, like this:

(format t "~s~%" list)

Now let’s see how it behaves:

CL-USER> (show-list (list 1 2 3 4))
(1 2 3 4)
(2 3 4)
(3 4)
(4)
NIL

That looks just like our original goal, so it looks like we got it right. Here’s the full program:

(defun longer-than-1 (list)
  (if (> (length list) 1) t))

(defun show-list (list)
  (format t "~s~%" list)
  (if (eql (longer-than-1 list) t)
      (show-list (rest list))
      nil))

Although I’m usually of the opinion “the shorter, the better” for functions, I’m not sure that we’re making things any simpler by moving the length test into the LONGER-THAN-1 function. I’m going to bring that logic into the SHOW-LIST function.

(defun show-list (list)
  (format t "~s~%" list)
  (if (> (length list) 1)
      (show-list (rest list))
      nil))

There. That’s definitely shorter and I think it’s actually a little clearer.

This entry was posted on Thursday, January 14th, 2010 at 4:23 pm and is filed under LISP. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.