This is a collection of blog entries written while learning Lisp. It is posted in the order written so you probably want to jump to the first post.

Monday, November 12, 2007

Chapter 3 problems revisited

I got some excellent feedback on my answers for the problems in chapter #3.

  • Try to not use length or reverse when possible as they have to traverse the list making it much slower then it could be.

  • Using cond over nested if statements makes for much easier to read code.

  • Rather then using loops, try to use recursion as the code is often smaller and easier to read.

Lastly I was trying to force the solutions into one function which was making it very hard. Splitting some of them into two makes it cleaner.

Some of the problems revisited:

2) Write a version of union that preserves the order of elements in the original lists (where the first list takes precedence over the second):
> (new-union '(a b c ) '(b a d))
(a b c d)

I modified the question to create a problem I could solve.

(defun new-union (lsta lstb)
(cond
((null lstb) lsta)
((not (eql nil (member (car lstb) lsta)))
(new-union lsta (cdr lstb)))
(t (new-union (append lsta (cons (car lstb) ())) (cdr lstb)))))

3) Define a function that take a list an returns a list indicating the number of times each (eql) element appears, sorted from most common element to least common:

Last time I tried to do this problem in just one function, which was turning out to be too hard so I used loops. But by splitting it into two it becomes very easy.

(defun occurrences (lst)
(occ-count (cdr (sort lst 'string<)) 1 (car lst)))

(defun occ-count (lst cnt x)
(cond
((null lst) (list (cons x cnt)))
((eql (car lst) x)
(occ-count (cdr lst) (+ 1 cnt) (car lst)))
(t (cons (cons x cnt) (occ-count (cdr lst) 1 (car lst))))))

5) Suppose the function pos+ takes a list and returns a list of each element plus its position:

> (pos+ '(7 5 1 4))
(7 6 3 7)

Last time I used maplist, but calling reverse and length would make it much slower then need be. Here is an alternative solution:

(defun pos+ (lst)
(bump 0 lst))

(defun bump (cnt lst)
(cond
((null lst) ())
(t (cons (+ cnt (car lst)) (bump (+ 1 cnt) (cdr lst))))))


On this last one I think that maplist might have been the solution the author was looking for (even if it wasn't that efficient) as it was covered in the chapter and it was the only problem where maplist fit.

4 comments:

Bruce -- said...

I think it's better to use recursion when it's a good fit and loops when they're a good fit. Recursion is not unconditionally better.

Here's an alternative pos+:

(defun pos+ (list)
(loop for i from 0
for n in list
collect (+ n i)))

Benjamin Meyer said...

:) I guess I was so intent upon using one of the functions introduced in the chapter I was oblivious to the simple solution.

Mikko said...

I think there is a bug in the problem 3:

* (occurrences '(e a b))

((E . 1) (B . 1) (E . 1))

Timothy Michael said...

The occurences function does not return the list sorted by the most occurences.

For instance:
(occurrences '(a a b b c c a d d d d d d))

((A . 3) (B . 2) (C . 2) (D . 6))

In order to sort them by occurrences you have to sort the list at the end like this:

(sort '((a . 3) (b . 2) (d . 4)) (lambda (x y) (> (cdr x) (cdr y))))