Problem 12

99 Haskell Problems

Problem 12

(**) Decode a run-length encoded list.

Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.

Example in Haskell:

P12> decodeModified 
       [Multiple 4 'a',Single 'b',Multiple 2 'c',
        Multiple 2 'a',Single 'd',Multiple 4 'e']
"aaaabccaadeeee"

Solution:

decodeModified :: (Eq a) => [CountElem a] -> [a]
decodeModified [] = []
decodeModified (x:xs) = (convertStr x)++(decodeModified xs)

convertStr :: (Eq a) => CountElem a -> [a]
convertStr (Single s) = buildstr 1 s
convertStr (Multiple n s) = buildstr n s

buildstr :: (Eq a) => Int -> a -> [a]
buildstr n s 
 | n == 0 = []
 | otherwise = s:(buildstr (n-1) s)

A more simple solution would be to use concatMap as shown in the solution of the problem.

decodeModified :: [CountElem a] -> [a]
decodeModified = concatMap decodeHelper
  where
    decodeHelper (Single x) = [x]
    decodeHelper (Multiple n x) = replicate n
The function concatMap takes two arguments, a function and a list. What it does is to use each element of the list as a input to the function and produce a corresponding list as a result. At the end all the resulting list is concatenated to become one list. By providing a function argument without the list for concatMap, we produce a new function that only take a list of a and produce a list of b by concatenate all the results.
:t concatMap
concatMap :: (a -> [b]) -> [a] -> [b]
Advertisements

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