Tuesday, June 24, 2008

Lisp problem 10: RLE of a list

This one worked out much easier, but again, I went at it non-recursively. Bitching about my struggles with the previous problems made me realise that I had solved most of the previous problems recursively but non-tail-recursively.
I guess there's a danger there of writing really poorly-performing functions on the assumption that the compiler will optimise them. Actually, I don't even know if SBCL does tail-call optimisation... It somehow seems easier to express tail-recursive solutions in Haskell, so far anyway - as a complete newbie to both languages.

;; P10: Run-length encoding of a list.
(defun encode (list)
(let ((chunked (pack list)) result)
(dolist (chunk chunked)
(setf result (append result
(list (list (length chunk) (car chunk))))))
result))


Oh yeah, how do you get around doing that ugly (append result (list (list x y))) stuff? I assume that's super slow, unless Lisp lists have a pointer to the last element for quick access since (you'd think?) appending is common. But then, some of the stuff I read in Practical Common Lisp suggests a push/reverse pattern, which to me seems a bit awkward.

No comments:

Post a Comment