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

From HaskellWiki

< 99 questions | Solutions

Lyklykkkkkkk (talk | contribs) (adding one more solution) |
|||

Line 51: | Line 51: | ||

| x == y = encode' (n + 1) x ys | | x == y = encode' (n + 1) x ys | ||

| otherwise = (n, x) : encode' 1 y ys | | otherwise = (n, x) : encode' 1 y ys | ||

+ | </haskell> | ||

+ | |||

+ | Or we can make use of zip and group: | ||

+ | |||

+ | <haskell> | ||

+ | import List | ||

+ | encode :: String -> [(Int, Char)] | ||

+ | encode xs=zip (map length l) h where | ||

+ | l = (group xs) | ||

+ | h = map head l | ||

</haskell> | </haskell> |

## Revision as of 06:34, 25 May 2012

(*) Run-length encoding of a list.

Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

```
encode xs = map (\x -> (length x,head x)) (group xs)
```

which can also be expressed as a list comprehension:

```
[(length x, head x) | x <- group xs]
```

Or writing it Pointfree (Note that the type signature is essential here to avoid hitting the Monomorphism Restriction):

```
encode :: Eq a => [a] -> [(Int, a)]
encode = map (\x -> (length x, head x)) . group
```

Or (ab)using the "&&&" arrow operator for tuples:

```
encode :: Eq a => [a] -> [(Int, a)]
encode xs = map (length &&& head) $ group xs
```

Or with the help of foldr (*pack* is the resulting function from P09):

```
encode xs = (enc . pack) xs
where enc = foldr (\x acc -> (length x, head x) : acc) []
```

Or using takeWhile and dropWhile:

```
encode [] = []
encode (x:xs) = (length $ x : takeWhile (==x) xs, x)
: encode (dropWhile (==x) xs)
```

Or without higher order functions:

```
encode [] = []
encode (x:xs) = encode' 1 x xs where
encode' n x [] = [(n, x)]
encode' n x (y:ys)
| x == y = encode' (n + 1) x ys
| otherwise = (n, x) : encode' 1 y ys
```

Or we can make use of zip and group:

```
import List
encode :: String -> [(Int, Char)]
encode xs=zip (map length l) h where
l = (group xs)
h = map head l
```