s-99-10

S-99-10 Run-length encoding of a list.

Use the result of problem S-99-09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

Example:

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

Solution:

We'll be using the higher order function map, which can be defined as:

 (define map 
   (lambda (f xs) 
     (if (null? xs) '() 
       (cons (f (car xs)) (map f (cdr xs)))))) 

The following helper function will return a list of the results of applying an encoder function to all elements in the list resulting from applying pack (see S-99-09) to the argument list xs:

 (define encode-f 
   (lambda (xs encoder) 
     (map encoder (pack xs)))) 

Finaly we can define the encode method by calling encode-f with an appropriate encoder function:

 (define encode 
   (lambda (xs) 
     (let ((encoder (lambda (pkg) 
                      (list (length pkg) (car pkg))))) 
       (encode-f xs encoder))))