Ninety-Nine Haskell Problems: #10

-- Implement the so-called run-length encoding data compression
-- method. Consecutive duplicates of elements are encoded as lists (N
-- E) where N is the number of duplicates of the element E:
-- "aaaabccaadeeee" ->
-- [(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

import Data.List

main :: IO ()
main = do
  putStrLn "Validity test results: "
  mapM_ (print . functionTester) testFunctions

testFunctions :: Eq a => [[a] -> [(Int, a)]]
testFunctions = [one
  , two
  , three
  , four
  , five]

testList :: [String]
testList = ["a", "aa", "ab", "aaa", "aab", "aba", "baa", "aaaa","aaab","aaba","aabb", "abbb"]

verificationList :: [[(Int, Char)]]
verificationList = [
    [(1,'a')]
  , [(2,'a')]
  , [(1,'a'),(1,'b')]
  , [(3,'a')]
  , [(2,'a'),(1,'b')]
  , [(1,'a'),(1,'b'),(1,'a')]
  , [(1,'b'),(2,'a')]
  , [(4,'a')]
  , [(3,'a'),(1,'b')]
  , [(2,'a'),(1,'b'),(1,'a')]
  , [(2,'a'),(2,'b')]
  , [(1,'a'),(3,'b')]]

functionTester :: (String -> [(Int, Char)]) -> Bool
functionTester function = verificationList == map function testList

-- Tested functions. Latency is measured in ticks. The size of the
-- test list for functionns one to four is 1000405 items, for the
-- fifth function, due to its ineffiency, its 10011 itmes.

-- 144
one :: Eq a => [a] -> [(Int, a)]
one = encode . group
  where
    encode = map (\x -> (length x, head x))

-- 163
two :: Eq a => [a] -> [(Int, a)]
two [] = []
two lst = foldr go [(1, last lst)] (init lst)
  where
    go i ((n, v):xs)
        | i == v = (n + 1, v) : xs
        | otherwise = (1, i) : (n, v) : xs

-- 155
three :: Eq a => [a] -> [(Int, a)]
three [] = []
three lst = reverse $ foldl go [(1, head lst)] (tail lst)
  where
    go ((n, v):xs) i
      | v == i = (n + 1, v) : xs
      | otherwise = (1, i) : (n, v) : xs

-- 79
four :: Eq a => [a] -> [(Int, a)]
four [] = []
four list = reverse $ go [(1, head list)] (tail list)
  where
    go acc [] = acc
    go ((n, v):xs) (y:ys)
      | v == y = go ((n + 1, v) : xs) ys
      | otherwise = go ((1, y) : (n, v) : xs) ys

-- 90 ticks; tested on a list with 10011 items.
five :: Eq a => [a] -> [(Int, a)]
five [] = []
five list = go [(1, head list)] (tail list)
  where
    go acc [] = acc
    go acc (y:ys)
      | (snd . last) acc == y =
        go (init acc ++ [(fst (last acc) + 1, snd (last acc))]) ys
      | otherwise = go (acc ++ [(1, y)]) ys

-- Validity check results:
-- True
-- True
-- True
-- True
-- True