Difference between revisions of "99 questions/Solutions/12"
< 99 questions | Solutions
Jump to navigation
Jump to search
m (I don't think "ugly code ahead" was necessary.) |
|||
(5 intermediate revisions by 3 users not shown) | |||
Line 24: | Line 24: | ||
<haskell> |
<haskell> |
||
toTuple :: ListItem a -> (Int, a) |
toTuple :: ListItem a -> (Int, a) |
||
− | toTuple (Single x) = (1, x) |
+ | toTuple (Single x) = (1, x) |
toTuple (Multiple n x) = (n, x) |
toTuple (Multiple n x) = (n, x) |
||
</haskell> |
</haskell> |
||
Line 31: | Line 31: | ||
<haskell> |
<haskell> |
||
− | + | decodeModified :: [ListItem a] -> [a] |
|
− | + | decodeModified = concatMap (uncurry replicate . toTuple) |
|
+ | </haskell> |
||
+ | |||
+ | a naïve solution with <hask>foldl</hask>: |
||
+ | <haskell> |
||
+ | decodeModified :: [ListItem a]-> [a] |
||
+ | decodeModified = foldl (\x y -> x ++ decodeHelper y) [] |
||
+ | where |
||
+ | decodeHelper :: ListItem a -> [a] |
||
+ | decodeHelper (Single x) = [x] |
||
+ | decodeHelper (Multiple n x) = replicate n x |
||
</haskell> |
</haskell> |
||
Line 38: | Line 48: | ||
<haskell> |
<haskell> |
||
− | + | decodeModified :: [ListItem a] -> [a] |
|
− | + | decodeModified = foldl (\acc e -> case e of Single x -> acc ++ [x]; Multiple n x -> acc ++ replicate n x) [] |
|
</haskell> |
</haskell> |
||
+ | |||
+ | |||
+ | [[Category:Programming exercise spoilers]] |
Revision as of 19:32, 18 January 2014
(**) 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:
decodeModified :: [ListItem a] -> [a]
decodeModified = concatMap (uncurry replicate . toTuple)
a naïve solution with foldl
:
decodeModified :: [ListItem a]-> [a]
decodeModified = foldl (\x y -> x ++ decodeHelper 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:
decodeModified :: [ListItem a] -> [a]
decodeModified = foldl (\acc e -> case e of Single x -> acc ++ [x]; Multiple n x -> acc ++ replicate n x) []