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.

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))))

Saturday, November 3, 2007

50 States

Over on reddit I saw the problem "Take the names of two U.S. States, mix them all together, then rearrange the letters to form the names of two other U.S. States. What states are these?"

At first I was going to code the (already presented) solution for the general case "Given a set of strings find two pair whom contain the same letter", but instead played around with the problem to see if I could find a faster solution which ended me with the following solution:

If you first sort each state and then sort the states you will find that four states sit next to one another (the exploitable property of the states set).
...
aachilnnoorrt (northcarolina)
aachilnoorstu (southcarolina)
...
aadhknoortt (northdakota)
aadhkoosttu (southdakota)
...

Then walk the list calculating the difference between the current word and the next word and store it in a list (haven't done hash yet in lisp) until you find a second duplicate difference in this case is "norsu"

This code could be cleaner and I think that I could write clean-states with map, but feel that I have spent a little too much time on this one problem so here is the code. A big problem I had with this was that I have no idea how to actually profile Lisp code. In C++ I would use valgrind. I will have to continue reading Practical Common Lisp to get to the chapter on packages so I can use the profiling packages. It was fun writing a larger problem in Lisp even when the fact that this is my first larger lisp program really shows.

(defun clean-states (lst)
(if (not lst)
nil
(cons (sort (copy-seq (car lst)) #'char<)
(clean-states (cdr lst)))))

(defun simplify (w &optional (s 0))
(if (> (+ 2 s) (length w))
w
(if (char= (char w s) (char w (+ 1 s)))
(simplify (concatenate 'string (subseq w 0 s) (subseq w (+ 2 s))) s)
(simplify w (+ 1 s)))))

(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<))))

(defun check (x lst)
(if (null lst)
nil
(let* ((y (first lst))
(dif (diff x y))
(sub (simplify dif)))
(let ((match (member sub *known* :test #'(lambda (x y) (string= x (car y))))))
(if (not match)
(progn
(push (cons sub (list x (first lst))) *known*)
;; (check x (cdr lst)) ;; enable this for the general solution
nil
)
(cdr (append (car match) (list x (first lst)))))))))

(defun find-match (lst)
(if (null lst)
nil
(let ((answer (check (car lst) (cdr lst))))
(if (not answer)
(find-match (cdr lst))
answer))))

(defun printout (words clean states)
(dolist (word words)
(loop for s in clean
for w in states
until (string= word s)
finally (return
(format t "~A " w)))))


(defvar *known* ())
(defun run ()
(setf *known* ())
(let* ((states '(
"alabama" "alaska" "arizona" "arkansas" "california" "colorado" "connecticut" "delaware" "florida" "georgia" "hawaii" "idaho" "illinois" "indiana" "iowa" "kansas" "kentucky" "louisiana" "maine" "maryland" "massachusetts" "michigan" "minnesota" "mississippi" "missouri" "montana" "nebraska" "nevada" "newhampshire" "newjersey" "newmexico" "newyork" "northcarolina" "northdakota" "ohio" "oklahoma" "oregon" "pennsylvania" "rhodeisland" "southcarolina" "southdakota" "tennessee" "texas" "utah" "vermont" "virginia" "washington" "westvirginia" "wisconsin" "wyoming"
))
(clean (clean-states states))
(results (find-match (sort (copy-list clean) #'string<))))
(printout results clean states)))

(run)