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.

Thursday, November 8, 2007

ANSI Common Lisp Chapter 3 : Lists

Chapter three starts off by going into more detail about how lists are made up and then dives into built in functions for manipulating lists. I must say that I find the map functions the most interesting as they are not often what you would find in c/c++ code. There is a brief introduction to keywords, but not enough to distract from the current lesson and a annotation with were the topic will be covered in the future.

Three of the introduced functions are union, intersection, and set-difference. This once again proves to me that I going through the books slowly learning what they have to offer will be very beneficial. The past weekend I was playing around and made the below function when I could have just used set-difference (my function assumes a and b are sorted).

(defun diff (a b)
(loop for x across a
for y across b
for i from 0
until (not (eq x y))
finally (return
(sort
(concatenate 'string (subseq a i) (subseq b i))
#'string<))))

We get an intro to functions for sequences, stacks, dotted lists, and accoc-lists. I enjoyed discovering the functions every and some, both functions that can only shine in a functional language. Putting it all together there was an example that found a shortest path with a breath-first algorithm. It took me a minute to follow everything that was going on, but it was a good example of how you could do quite a bit with lists (in very little code too).

Lastly at the end of each chapter in the book there is a "Summary" section. Where when I found myself not already knowing one of the points I went back and read the section. A nice touch to the book I think. Except this one which seems kinda silly as a summary point:

"Run length encoding is a simple compression algorithm for use in resaurants"

ANSI Common Lisp so far has been about how to solve tasks in lisp in comparison to the first few chapters of Practical Common Lisp which concentrated on the actual language features. I am not sure which method I like more. I like Practical Common Lisp's approach because it would introduce neat features and would get me all fired up to want to use them (and tell people about them). But at the same time I see value in ANSI Common Lisps approach of building a base of familiar functions before introducing features found only in Lisp. Reading both books is the best of both worlds :)

Exercises

1) Skipping this one because it wants drawings.

2) Write a version of union that preserves the order of elements in the original lists:
> (new-union '(a b c ) '(b a d))
(a b c d)

Not sure how to solve this sense even in the given example 'b is coming after 'a which does not preserve the order of the elements in the second list. Anyone?

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:

> (occurrences '(a b a d a c d c a))
((A . 4) (C . 3) (D . 3) (B . 1))

This one took me way to long to figure out. I kept trying to do it recursively, but was unable to because you can't use setf on every function I know like member and assoc. If you can solve this recursively please feel free to submit your solution in the comments.

(defun occurrences (lst)
(do ((i 0 (+ i 1))
(rst ()))
((> (+ 1 i) (length lst))
(reverse (sort rst '< :key #'cdr)))
(let ((cur (nth i lst)))
(if (not (member cur rst :key #'car))
(push (cons cur (count cur lst)) rst)))))

4) Why does (member '(a) '((a) (b)))) return nil

Because eql only returns true if the args are the same object or numbers or charector with the same value. None of which are true.

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)

(defun pos+ (lst)
(let ((rev (reverse lst)))
(reverse (maplist #'(lambda (x) (+ (car x) (length (cdr x)))) rev))))

6) After years of deliberation, a government commission has decided that lists should be represented by using the cdr to point to the first element and the car to point to the rest of the list. Define the government version of the following functions:

(a) cons
(b) list
(c) length(for lists)
(d) member (for lists; no keywords)

a) (defun gov-cons(x y) (cons y x))
b) (defun gov-list (list &rest other)
(if (null list)
()
(gov-cons list (gov-list (car other) (cdr other)))))
Although I had to look up how rest worked in Practical Common Lisp, ANSI Common Lisp hasn't covered it yet.
c) (defun gov-length (lst)
(if (null lst)
0
(+ 1 (gov-length (car lst)))))
d)(defun gov-member (item lst)
(if (null lst)
nil
(if (eql (cdr lst) item)
lst
(gov-member item (car lst)))))

7) Modify the program in FIgure 3.6 to use fewer cons cells. (Hint Use dotted lists)

(defun compress (x)
(if (consp x)
(compr (car x) 1 (cdr x))
x))
(defun compr (elt n lst)
(if (null lst)
(if (> n 1)
(cons n elt)
(cons n ()))
(let ((next (car lst)))
(if (eql next elt)
(compr elt (+ n 1) (cdr lst))
(cons (n-elts elt n)
(compr next 1 (cdr lst)))))))
(defun n-elts (elt n)
(if (> n 1)
(cons n elt)
elt))

8) Define a function that take a list and prints it in dot notation:
> (showdots '(a b c))
(A . (B . (C . NIL)))
NIL

(defun showdots (lst)
(do ((i 0 (+ i 1)))
((> (+ 1 i) (length lst))
(format t " NIL"))
(format t "\(~A ." (nth i lst)))
(do ((i 0 (+ i 1)))
((> (+ 1 i) (length lst)))
(format t "\)")))

9) Write a program to find the longest finite path with no duplicates through a network represented as in Section 3.15. The network may contain cycles.

(setf min '((a b c) (b c) (c d)))

(defun longest-path (start end net)
(bfs end (list (list start)) net ()))

(defun bfs (end queue net best)
(if (null queue)
best
(let ((path (car queue)))
(let ((node (car path)))
(bfs end
(if (eql 1 (count node path))
(append (cdr queue)
(new-paths path node net))
(cdr queue))
net
(if (eql node end)
(if (> (length path) (length best))
(reverse path)
best)))))))

(defun new-paths (path node net)
(mapcar #'(lambda (n)
(cons n path))
(cdr (assoc node net))))

2 comments:

Liron said...

Hi stranger, thanks for posting longest-path, i was implementing some horrible dfs algorithm with setf's to keep track of state, and i knew there must have been a better way.

However, you forgot to check the case where a node is its own child (possible with cycles). So if the path discovers a cycle, then it should not do the length comparison between path and best. So here's a quick fix (i used let* for convenience):

(defun bfs (end queue net best)
(if (null queue)
best
(let* ((path (car queue)) (node (car path)) (nocycle (eql 1 (count node path))))
(bfs end
(if nocycle
(append (cdr queue)
(new-paths path node net))
(cdr queue))
net
(if (and (> (length path) (length best)) nocycle)
(reverse path)
best)))))

I hope the formatting doesn't come out atrociously. On to chapter 4!

hrtmtbrng said...

Hi Lisp-Friend!
I am learning Lisp, too. Thank you for your blog! I have a recursive solution for excercise three. Not ideal because it still uses setf, but recursive. You only have to sort this. See here:

(defun occurrences (lst)
(if (null lst)
nil
(let ((occs (occurrences(cdr lst))))
(if (assoc (car lst) occs)
(let ((occ (assoc (car lst) occs)))
(setf (cdr occ) (+ (cdr occ) 1))
occs)
(cons (cons (car lst) 1) occs )))))