Scheme run length encoding

Question

The problem is to:

Write a function (encode L) that takes a list of atoms L and run-length encodes the list such that the output is a list of pairs of the form (value length) where the first element is a value and the second is the number of times that value occurs in the list being encoded.

For example:

(encode '(1 1 2 4 4 8 8 8)) ---> '((1 2) (2 1) (4 2) (8 3))

This is the code I have so far:

(define (encode lst)
  (cond 
    ((null? lst) '())
    (else ((append (list (car lst) (count lst 1)) 
                   (encode (cdr lst)))))))

(define (count lst n)
  (cond 
    ((null? lst) n)
    ((equal? (car lst) (car (cdr lst))) 
      (count (cdr lst) (+ n 1)))
    (else (n)))))

So I know this won't work because I can't really think of a way to count the number of a specific atom in a list effectively as I would iterate down the list. Also, Saving the previous (value length) pair before moving on to counting the next unique atom in the list. Basically, my main problem is coming up with a way to keep a count of the amount of atoms I see in the list to create my (value length) pairs.

Answer 1

You need a helper function that has the count as additional argument. You check the first two elements against each other and recurse by increasing the count on the rest if it's a match or by consing a match and resetting count to 1 in the recursive call.

Here is a sketch where you need to implement the <??> parts:

(define (encode lst)
  (define (helper lst count)
    (cond ((null? lst) <??>)
          ((null? (cdr lst)) <??>))
          ((equal? (car lst) (cadr lst)) <??>)
          (else (helper <??> <??>))))
  (helper lst 1))

;; tests
(encode '())              ; ==> ()
(encode '(1))             ; ==> ((1 1))
(encode '(1 1))           ; ==> ((1 2))
(encode '(1 2 2 3 3 3 3)) ; ==> ((1 1) (2 2) (3 4))

Using a named let expression

This technique of using a recursive helper procedure with state variables is so common in Scheme that there's a special let form which allows you to express the pattern a bit nicer

(define (encode lst)
  (let helper ((lst lst) (count 1))
    (cond ((null? lst) <??>)
          ((null? (cdr lst)) <??>))
          ((equal? (car lst) (cadr lst)) <??>)
          (else (helper <??> <??>)))))

---

Comments on the code in your question: It has excess parentheses..

((append ....)) means call (append ....) then call that result as if it is a function. Since append makes lists that will fail miserably like ERROR: application: expected a function, got a list.

(n) means call n as a function.. Remember + is just a variable, like n. No difference between function and other values in Scheme and when you put an expression like (if (< v 3) + -) it needs to evaluate to a function if you wrap it with parentheses to call it ((if (< v 3) + -) 5 3); ==> 8 or 2