Q4: Run-Length Encoding

Run-length encoding is a very simple data compression technique, whereby runs of data are compressed and stored as a single value. A run is defined to be a contiguous sequence of the same number. For example, in the (finite) sequence

1, 1, 1, 1, 1, 6, 6, 6, 6, 2, 5, 5, 5 

there are four runs: one each of 1, 6, 2, and 5. We can represent the same sequence as a sequence of two-element lists:

(1 5), (6 4), (2 1), (5 3) 

Notice that the first element of each list is the number in a run, and the second element is the number of of times that number appears in the run.

We will extend this idea to streams. Write a function called rle that takes in a stream of data, and returns a corresponding stream of two-element lists, which represents the run-length encoded version of the stream. You do not have to consider compressing infinite runs.

scm> (define s (cons-stream 1 (cons-stream 1 (cons-stream 2 nil)))) s scm> (define encoding (rle s)) encoding scm> (car encoding) ; Run of number 1 of length 2 (1 2) scm> (car (cdr-stream encoding)) ; Run of number 2 of length 1 (2 1) scm> (stream-to-list (rle (list-to-stream '(1 1 2 2 2 3)))) ; See functions in lab13.scm ((1 2) (2 3) (3 1)) (define (rle s) 'YOUR-CODE-HERE ) 

Help? Can someone with a knowledge of scheme help?