Pascal J. Bourguignon wrote:

> and my solutions (still incomplete):
> http://www.informatimago.com/develop/lisp/l99/index.html

Where we find:

(---------------------------------------------------------------
P13 (**) Run-length encoding of a list (direct solution).

Example:
* (encode-direct '(a a a a b c c a a d e e e e))
((4 A) B (2 C) (2 A) D (4 E))
"

;; Iterative solution, uses only O(r) space:

(defun encode-modified (list)
(let ((result '())
(count 0)
(last-item nil))
(labels ((collect-result ()
(push (if (= 1 count)
last-item
(list count last-item))
result))
(new-item (item)
(setf count 1
last-item item))
(same-item ()
(incf count))
(return-result ()
(when (plusp count)
(collect-result))
(nreverse result)))
(dolist (item list (return-result))
(cond
((zerop count) (new-item item))
((eql item last-item) (same-item))
(t (collect-result)
(new-item item)))))))
---------------------------------------------------------------)

Gauche Scheme or Racket:

(require srfi/1) ;; fold-right for Racket

(define (encode the-list)
(define (increment n item) (list (+ 1 n) item))
(define (update xs . accum) (cons (apply increment xs) accum))
(define (kons x accum)
(if (or (null? accum) (not (equal? x (cadar accum))))
(cons (list 1 x) accum)
(apply update accum)))
(map
(lambda (xs) (if (= 1 (car xs)) (cadr xs) xs))
(fold-right
kons
'()
the-list)))

(encode '(a a a a b c c a a d e e e e))
===>
((4 a) b (2 c) (2 a) d (4 e))