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

Line 20: | Line 20: | ||

First of all we could rewrite the function <hask>encode</hask> from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using <hask>foldr</hask>) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function <hask>encodeModified</hask> from problem 11 to use <hask>encode'</hask>. |
First of all we could rewrite the function <hask>encode</hask> from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using <hask>foldr</hask>) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function <hask>encodeModified</hask> from problem 11 to use <hask>encode'</hask>. |
||

+ | |||

+ | |||

+ | Alternative direct writing without significant external functions: |
||

+ | <haskell> |
||

+ | encodeDirect :: (Eq a) => [a] -> [ListItem a] |
||

+ | encodeDirect [] = [] |
||

+ | encodeDirect (x:xs) = encodeDirect' 1 x xs |
||

+ | encodeDirect' n y [] = [encodeElement n y] |
||

+ | encodeDirect' n y (x:xs) | y == x = encodeDirect' (n+1) y xs |
||

+ | | otherwise = encodeElement n y : (encodeDirect' 1 x xs) |
||

+ | encodeElement 1 y = Single y |
||

+ | encodeElement n y = Multiple n y |
||

+ | </haskell> |

## Revision as of 21:40, 25 October 2011

(**) Run-length encoding of a list (direct solution).

Implement the so-called run-length encoding data compression method directly. I.e. don't explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem P11, simplify the result list by replacing the singleton lists (1 X) by X.

```
encode' :: Eq a => [a] -> [(Int,a)]
encode' = foldr helper []
where
helper x [] = [(1,x)]
helper x (y@(a,b):ys)
| x == b = (1+a,x):ys
| otherwise = (1,x):y:ys
encodeDirect :: Eq a => [a] -> [ListItem a]
encodeDirect = map encodeHelper . encode'
where
encodeHelper (1,x) = Single x
encodeHelper (n,x) = Multiple n x
```

First of all we could rewrite the function `encode`

from problem 10 in a way that is does not create the sublists. Thus, I decided to traverse the original list from right to left (using `foldr`

) and to prepend each element to the resulting list in the proper way. Thereafter we only need to modify the function `encodeModified`

from problem 11 to use `encode'`

.

Alternative direct writing without significant external functions:

```
encodeDirect :: (Eq a) => [a] -> [ListItem a]
encodeDirect [] = []
encodeDirect (x:xs) = encodeDirect' 1 x xs
encodeDirect' n y [] = [encodeElement n y]
encodeDirect' n y (x:xs) | y == x = encodeDirect' (n+1) y xs
| otherwise = encodeElement n y : (encodeDirect' 1 x xs)
encodeElement 1 y = Single y
encodeElement n y = Multiple n y
```