(A really quick post today). Following a recent post, Run length encoding in Python, I thought it would be nice to look at this simple encoding in Haskell. The RLE idea is simple, given some input:
"aaaabbaaa"
compress it by taking the length of each run of characters:
"4a2b3a"
Running this in GHCi:
> encode "aaaabbaaa" [(4,'a'),(2,'b'),(3,'a')] > decode (encode "aaaabbaaa") "aaaabbaaa"
So there’s a simple QuickCheck property we’ll want to establish. First, let’s look at the Python implementations:
def encode(l):
return [(len(list(group)),name) for name, group in groupby(l)]
def decode(l):
return sum([length * [item] for length,item in l],[])
Ok, so group each run into a list, then pair up the length, with the list item, and to decode, replicate the character by its length, and concatenate. Easy in Haskell:
encode = map (length &&& head) . group decode = concatMap (uncurry replicate)
Who says static typing implies verbosity?
We also get a generic implementation for free, given that Haskell infers that the code never inspects the elements in the list directly, our `encode’ function will just as happily encode Strings as lists of numbers or any other list. That is, ‘encode’ will work on any type `a’ that looks like it can do (==).
encode :: Eq a => [a] -> [(Int, a)]
So:
> encode [1,1,1,1,2,2,2,7,7] [(4,1),(3,2),(2,7)] > encode ["foo", "foo", "bar", "foo", "foo", "foo"] [(2,"foo"),(1,"bar"),(3,"foo")]
Polymorphism rocks.
The original poster used a couple of unit tests, but in Haskell we’d usually specify generic properties the function must satisfy:
prop_id :: String -> Bool prop_id xs = decode (encode xs) == xs
QuickCheck then generates input for us:
> quickCheck prop_id
OK, passed 100 tests.
So go out and sketch your little algorithms in (shorter, faster, safer) pseudo-Python :-)
Thanks to psykotic for the idea!
