Programming Praxis – Run Length Encoding

In today’s Programming Praxis exercise we have to implement a run length encoding algorithm. The provided Scheme solution weighs in at 27 lines. Let’s see if we can do any better in Haskell.

First, two imports.

import Data.List
import Data.List.Split

Compressing is easy: use group and chunk to separate the string into runs of the appropriate length and then apply tilde encoding as necessary.

compress :: String -> String
compress s = f =<< chunk 26 =<< group s where
    f xs = if length xs < 4 && take 1 xs /= "~" then xs
           else '~' : toEnum (length xs + 64) : take 1 xs

Expanding is easier still and can be done entirely through pattern matching.

expand :: String -> String
expand []           = []
expand ('~':r:c:xs) = replicate (fromEnum r - 64) c ++ expand xs
expand (c:xs)       = c : expand xs

And of course we have to test if everything works correctly.

main :: IO ()
main = do print $ compress org == rle
          print $ expand rle == org
                rle = "ABBB~A~C~ED~ZE~DE"

Everything seems to be working and at 6 lines that’s 4,5 times shorter than the Scheme solution. Not bad.

Tags: , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: