#24: Run-Length Encoding

Tagged as challenge

Written on 2018-01-30

Part 1

Write a function rle :: [Integer] -> [(Integer, Integer)] to compute the run-length encoding of a list of integers. The result is a list of (<item>, <run-length>) pairs. Here are some test cases.

(rle '())                  ; => ()
(rle '(1))                 ; => ((1 1))
(rle '(1 1 1 2 2 3 2 3 3)) ; => ((1 3) (2 2) (3 1) (2 1) (3 2))

Try using your language's fold function and/or write in a functional fashion.

Part 2

Run-length encoding can be applied to infinite streams as well, producing run-length encoded output. However, the function would never terminate if we were, say, given an infinite stream of 1's. As such, we might want to bound the size of the output run-lengths.

Write a function rle' whose type, written in Standard ML notation, is

​ (int option) * (int stream) -> (int, int) stream.

The first argument is an option type, which will be None if we should allow unbounded run-lengths, and Some n which bounds the run-lengths to at most n, a positive integer. Here are some test cases in Haskell:

take 1 $ rle' None (repeat 1)               -- never terminates
rle' None <finite list>                     -- equal to: rle <finite-list>
take 2 $ rle' None [1, 1, 1, 2, 2, ...]     -- [(1, 3), (2, 2)]
take 3 $ rle' (Some 2) [1, 1, 1, 2, 2, ...] -- [(1, 2), (1, 1), (2, 2)]
rle' (Some n) (repeat x)                    -- equal to: repeat (x, n)

• ← Previous
• Next →