S-99-12


S-99-12 Decode a run-length encoded list.

Given a run-length code list generated as specified in problem S-99-11. Construct its uncompressed version.

Example:

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

Solution:

 (define map-append 
   (lambda (f xs) 
     (if (null? xs) '() 
       (append (f (car xs)) (map-append f (cdr xs)))))) 
  
 (define decode-f 
   (lambda (xs decoder) 
     (map-append decoder xs))) 
  
 (define decode 
   (lambda (xs) 
     (letrec ((expand (lambda (N E) 
                        (if (= N 0) '() 
                          (cons E (expand (- N 1) E))))) 
              (decoder (lambda (code) 
                         (if (pair? code) (expand (car code) (cadr code)) 
                           (list code))))) 
       (decode-f xs decoder))))