# Difference between revisions of "99 questions/Solutions/12"

From HaskellWiki

< 99 questions | Solutions

m (I don't think "ugly code ahead" was necessary.) |
Lyklykkkkkkk (talk | contribs) (submitting a solution) |
||

Line 33: | Line 33: | ||

decode :: [ListItem a] -> [a] | decode :: [ListItem a] -> [a] | ||

decode = concatMap (uncurry replicate . toTuple) | decode = concatMap (uncurry replicate . toTuple) | ||

+ | </haskell> | ||

+ | |||

+ | a naïve solution with <hask>foldl</hask>: | ||

+ | <haskell> | ||

+ | decode :: Eq a =>[ListItem a]-> [a] | ||

+ | decode = foldl (\x y -> x ++ dh y) [] | ||

+ | where | ||

+ | decodeHelper :: Eq a => ListItem a -> [a] | ||

+ | decodeHelper (Single x)=[x] | ||

+ | decodeHelper (Multiple n x)= replicate n x | ||

</haskell> | </haskell> | ||

## Revision as of 02:58, 26 May 2012

(**) 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 :: Eq a =>[ListItem a]-> [a]
decode = foldl (\x y -> x ++ dh y) []
where
decodeHelper :: Eq a => 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) []
```