Run-length encoding in Haskell

Question

I wrote a short Haskell script to compress and decompress via the use of run length encoding.

The concept is simple enough, n equal items x in a row will be replaced by (n, x), decompressing is just the reverse.

For example:

> runLengthCompress "foooo barrr"
[(1,'f'),(4,'o'),(1,' '),(1,'b'),(1,'a'),(3,'r')]

As you can see the four consecutive o have been substituted by (4,'o')

About the code itself I fear I have written too little points (arguments) to my functions, hindering readability but I am not sure, maybe the lack of points makes it more readable, not less.

Also I feel like my areInverses function is already built-in into Haskell and that I am rebuilding the wheel with it.

Without further ado, here is the code:

import Data.List
import Control.Monad
import Control.Arrow
runLengthExpand :: [(Int, a)] -> [a]
runLengthExpand = concat . map (uncurry replicate)
runLengthCompress :: Eq a => [a] -> [(Int, a)]
runLengthCompress = (map (length &&& head)) . group
areInverses :: Eq b => (a -> b) -> (b -> a) -> [b] -> Bool
areInverses f g = all ((==) =<< f . g)
examples :: [[Int]]
examples = [ [3, 3, 3, 5, 5, 7, 1], [1,1,1,0,0,0,5] ]
main :: IO()
main = do
 print $ runLengthCompress "foooo barrr"
 print $ areInverses runLengthExpand runLengthCompress examples

• Gurkenglas: lpaste.net/5825040676416389120 - hlint is your friend. Try quickcheck to get things like your areInverses.

Answer 1

You want to import only the functions you're actually going to need:

import Data.List (group)
import Control.Arrow ((&&&))

As Gurkenglas already said, use concatMap instead of concat . map. This leads to

runLengthExpand :: [(Int, a)] -> [a]
runLengthExpand = concatMap (uncurry replicate)

Your runLengthCompress is fine, although (&&&) might not be known to newcomers.

Now, areInverses is too obfuscated:

About the code itself I fear I have written too little points (arguments) to my functions, hindering readability but I am not sure, maybe the lack of points makes it more readable, not less.

Pointfree style isn't necessarily easier to read:

5 Problems with pointfree

Point-free style can (clearly) lead to Obfuscation when used unwisely.

We can split its functionality in multiple functions:

isInverseOn :: Eq a => (a -> b) -> (b -> a) -> a -> Bool
isInverseOn f g x = x == g (f x)
areInverses :: Eq a => (a -> b) -> (b -> a) -> [a] -> Bool
areInverses f g = all (isInverseOn f g)

This removes the need for =<< completely and is easier to read than your previous (==) =<< f . g.

However, that only checks whether g is an inverse of f, not whether f is the inverse of g. For example, g's codomain might not be the completely covered by f's domain. So a proper areInverses should also check isInverseOn g f for some appropriate values.

You can use QuickCheck to generate appropriate strings and lists of pairs, although you need to generate the latter by hand.