(module rle mzscheme
  (require (lib "list.ss")
           (lib "etc.ss")
           (lib "contract.ss")
           (planet "comprehensions.ss" ("dyoo" "srfi-alias.plt" 1)))
  
  (define encoding/c? (listof (list/c number? char?)))
  
  (provide/contract [rle-encode (string? . -> . encoding/c?)]
                    [rle-decode (encoding/c? . -> . string?)])
  
  ;; rle-encode: string -> (listof (list number char))
  ;; Calculates a run-length encoding of the string.
  (define (rle-encode a-string)
    (local ((define L (string-length a-string)))
      (cond
        [(= L 0)
         empty]
        [else
         (let loop ([i 1]
                    [last-char (string-ref a-string 0)]
                    [run 1])
           (cond
             [(= i L)
              `((,run ,last-char))]
             [else
              (local ((define next-char (string-ref a-string i)))
                (cond
                  [(char=? last-char next-char)
                   (loop (add1 i) last-char (add1 run))]
                  [else
                   (cons `(,run ,last-char)
                         (loop (add1 i) next-char 1))]))]))])))
  
  ;; Reconstitutes a rle-encoded representation back into a string.
  (define (rle-decode an-encoding)
    (string-append-ec (:list n&c an-encoding) (apply make-string n&c))))