Tagged as challenge

Written on 2018-01-30

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.

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)
```