Compressing by counting repetitive elements (Haskell)

Question

I'm looking for a straight-forward combination of standard higher-order functions to compress a list by counting repetitive elements. For example the result for

"abbccccb"

would be :

 [(1, 'a'), (2, 'b'), (4, 'c'), (1, 'b')] 

another example, the result for

(sort "abrakadabra") 

would be:

[(5, 'a'), (2, 'b'), (1, 'd'), (1, 'k'), (2, 'r')]

Answer 1

I wrote a code that only makes use of elementary functions.

f :: Eq a => [a] -> [(Int, a)]
f [] = []
f (x:xs) = (1 + length (takeWhile (==x) xs), x) : f (dropWhile (==x) xs)

I hope this will help!.

Answer 2

Start by using Data.List.group. This gives you a list of runs of equal elements, e.g.

> group "abbccccb"
["a","bb","cccc","b"]

Then, map over this list, taking the head and length of each run. This can be done elegantly with the &&& operator from Control.Arrow:

> map (length &&& head) . group $ "abbccccb"
[(1,'a'),(2,'b'),(4,'c'),(1,'b')]

Answer 3

You could also use Control.Applicative and the applicative functor instance of (->) e

map ((,) <$> length <*> head) . group

If you now wanted a triple with the ord value, it's really easy!

map ((,,) <$> length <*> head <*> ord . head) . group

However an anonymous function is probably clearer to the reader.

map (\xs -> (length xs, head xs, (ord . head) xs) . group