Personal tools

99 questions/Solutions/12

From HaskellWiki

Jump to: navigation, search

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

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

decodeModified :: [ListItem a] -> [a]
decodeModified = concatMap decodeHelper
    where
      decodeHelper (Single x)     = [x]
      decodeHelper (Multiple n x) = replicate n x

We only need to map single instances of an element to a list containing only one element and multiple ones to a list containing the specified number of elements and concatenate these lists.

A solution for the simpler encoding from problem 10 can be given as: 

decode :: [(Int, a)] -> [a]
decode = concatMap (uncurry replicate)

This can be easily extended given a helper function: 

toTuple :: ListItem a -> (Int, a)
toTuple (Single x) = (1, x)
toTuple (Multiple n x) = (n, x)

as: 

decode :: [ListItem a] -> [a]
decode = concatMap (uncurry replicate . toTuple)
a naïve solution with
foldl
: 
decode :: [ListItem a]-> [a]
decode = foldl (\x y -> x ++ dh y) [] 
    where
        decodeHelper :: ListItem a -> [a]
        decodeHelper (Single x)=[x]
        decodeHelper (Multiple n x)= replicate n x
foldl
can also be used to solve this problem: 
decode :: [ListItem a] -> [a]
decode = foldl (\acc e -> case e of Single x -> acc ++ [x]; Multiple n x -> acc ++ replicate n x) []
Retrieved from "http://www.haskell.org/haskellwiki/99_questions/Solutions/12"