Binary search and dumb compression in Common Lisp

In my quest to learn lisp, I've been alternating scheme and common lisp readings and lectures.

I find scheme really enlightening, but quite difficult to write in it. Maybe it's because I haven't officially reached the set! chapter in SICP, and I still find difficult to write (so) functional code.

The point is that I finished this book and then, I started Paul Graham's ANSI Common Lisp. I've been really enjoying this reading, because it shows you interesting things (from an experienced programmer point of view) from the very beginning.

During the first 3 or 4 chapters, threre are some code examples, that I've tried to write on my own (maybe grasping a bit on graham's code when I got stuck, but well)

First, here's a compress/decompress lists lisp code. When entered a list like (0 0 0 1 2 1 1 0 4 4), compress returns a list of atoms or lists themselves, that contain the number of repetitions and the value to repeat: ((3 0) 1 2 (2 1) 0 (2 4)) . It's nice to see that at such low level point, being able to ask for a type of a given element gives us enough power to code this in a very simple way. I don't even want to think how I'd code it in java/c++.

Decompress does obviously the reverse operation

	;; '(0 0 1 0 0) => ((2 0) 1 (2 0))
	;; CL-USER> (compress '(3 3 4 3 3 2 1 1 1 1 0))
	;; ((2 3) 4 (2 3) 2 (4 1) 0)
	(defun compress (l1)
	(cond ((null (cdr l1)) '())
	(t (accum (car l1) 1 (cdr l1)))))
	(defun accum (val acc lst)
	(cond ((null lst) (cons (comp-list val acc) nil))
	((eq val (car lst)) (accum val (1+ acc) (cdr lst)))
	(t (cons (comp-list val acc) (accum (car lst) 1 (cdr lst))))))
	(defun comp-list (val acc)
	(if (> acc 1) (list acc val) val))
	(defun decompress (lst)
	(cond ((null lst) nil)
	((atom (car lst)) (cons (car lst) (decompress (cdr lst))))
	((consp (car lst)) (append (deep-decompress (car lst)) (decompress (cdr lst)))
	)))
	(defun deep-decompress (lst)
	(if (zerop (car lst)) nil
	(cons (second lst) (deep-decompress (list (1- (car lst)) (second lst))))))

view raw compress.lisp hosted with ❤ by GitHub

The binary search is just what its name says. Does a binary recursive search on an already sorted vector (array of 1 x N dimension).

	(defun bin-search (obj vect)
	(bin-search-rec obj vect 0 (1- (length vect))))
	(defun bin-search-rec (obj vec start end)
	(let* ((range (- end start))
	(mid (+ start (round (/ range 2)))))
	(cond ((eq (aref vec mid) obj) (format t "l'hem trobat a la posicio blabla ~A" mid))
	((zerop range) nil)
	((< (aref vec mid) obj) (bin-search-rec obj vec (1+ mid) end))
	((> (aref vec mid) obj) (bin-search-rec obj vec start (1- mid))))))

view raw binsearch.lisp hosted with ❤ by GitHub

I'm getting very fond of 'cond'. It takes the best things of both if and switch/case worlds. A switch-case like syntax, with powerful conditionals (not just comparing with '=')

That's all for now. Sorry for the crappy gists code listings. it seems github doesn't know much about common lisp (syntax nor indenting).

Btw, I've received my SICP copy in dead-tree format, so I'll probably spend some time with scheme when I finish Ansi Common Lisp.