Problem 13

99 Haskell Problems

Problem 13

(**) Run-length encoding of a list (direct solution).

Implement the so-called run-length encoding data compression method directly. I.e. don’t explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.

Example:

* (encode-direct '(a a a a b c c a a d e e e e))
((4 A) B (2 C) (2 A) D (4 E))

Example in Haskell:

P13> encodeDirect "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',
 Multiple 2 'a',Single 'd',Multiple 4 'e']

Solution:

encodeDirect :: (Eq a) => [a] -> [CountElem a]
encodeDirect [] = []
encodeDirect (x:xs) = encodeDirect1 1 x xs

encodeDirect1 :: (Eq a) => Int -> a -> [a] -> [CountElem a]
encodeDirect1 n x [] = [encodeElem n x]
encodeDirect1 n x xs
 | x == (head xs) = encodeDirect1 (n+1) x (tail xs)
 | otherwise = [(encodeElem n x)] ++ (encodeDirect1 1 (head xs) (tail xs))

encodeElem :: (Eq a) => Int -> a -> CountElem a
encodeElem n x
 | n == 1 = Single x
 | otherwise = Multiple n x

I am not sure I am doing this directly. but I didn’t intent to create a sublist.

Advertisements