Posts Tagged ‘length’

Programming Praxis – Hett’s Problem 1.28

August 9, 2011

In today’s Programming Praxis, our goal is to sort a list of lists by length and by length frequency. Let’s get started, shall we?

A quick import:

import qualified Data.List.Key as K

Sorting by length is trivial.

byLength :: [[a]] -> [[a]]
byLength = K.sort length

Sorting by frequency of the list lengths is a bit more complicated since we need to group and ungroup the lists, but still a one-liner.

byLengthFreq :: [[a]] -> [[a]]
byLengthFreq = concat . byLength . length . byLength

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ byLength ["abc","de","fgh","de","ijkl","mn","o"]
                        == ["o","de","de","mn","abc","fgh","ijkl"]
          print $ byLengthFreq ["abc","de","fgh","de","ijkl","mn","o"] 
                            == ["o","ijkl","abc","fgh","de","de","mn"]

Programming Praxis – Run Length Encoding

February 26, 2010

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.