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
          where org = "ABBB~CDDDDDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE"
                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.

About these ads

Tags: , , , , , , , ,

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: