s-99-13


S-99-13 Run-length encoding of a list (direct solution).

Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem S-99-09, but only count them. As in problem S-99-11, simplify the result list by replacing the singleton lists (1 X) by X.

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

Solution:

 (define encode-direct 
   (lambda (xs) 
     (if (null? xs) '() 
       (let ((pkg (lambda (N E) 
                    (if (= N 1) E (list N E))))) 
         (let loop ((rest (cdr xs)) 
                    (E (car xs)) 
                    (N 1)) 
           (cond ((null? rest) 
                  (list (pkg N E))) 
                 ((eq? E (car rest)) 
                  (loop (cdr rest) E (+ N 1))) 
                 (else 
                   (cons (pkg N E) (loop (cdr rest) (car rest) 1)))))))))