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

Lyklykkkkkkk (talk | contribs) (adding one more solution) |
m (fix omission of function "group" in offered alternate list comprehension) |
||

(7 intermediate revisions by 5 users not shown) | |||

Line 11: | Line 11: | ||

<haskell> |
<haskell> |
||

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

+ | </haskell> |
||

+ | |||

+ | or |
||

+ | |||

+ | <haskell> |
||

+ | [(length (x:xs), x) | (x:xs) <- group xs] |
||

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

Line 25: | Line 31: | ||

encode :: Eq a => [a] -> [(Int, a)] |
encode :: Eq a => [a] -> [(Int, a)] |
||

encode xs = map (length &&& head) $ group xs |
encode xs = map (length &&& head) $ group xs |
||

+ | </haskell> |
||

+ | |||

+ | Or using the slightly more verbose (w.r.t. <hask>(&&&)</hask>) Applicative combinators: |
||

+ | |||

+ | <haskell> |
||

+ | encode :: Eq a => [a] -> [(Int, a)] |
||

+ | encode = map ((,) <$> length <*> head) . pack |
||

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

Line 57: | Line 70: | ||

<haskell> |
<haskell> |
||

import List |
import List |
||

− | encode :: |
+ | encode :: Eq a => [a] -> [(Int, a)] |

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

l = (group xs) |
l = (group xs) |
||

h = map head l |
h = map head l |
||

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

+ | |||

+ | Or if we ignore the rule that we should use the result of P09, |
||

+ | |||

+ | <haskell> |
||

+ | encode :: Eq a => [a] -> [(Int,a)] |
||

+ | encode xs = foldr f final xs Nothing |
||

+ | where |
||

+ | f x r (Just a@(i,q)) | x == q = r (Just (i+1,q)) |
||

+ | | otherwise = a : r (Just (1, x)) |
||

+ | f x r Nothing = r (Just (1, x)) |
||

+ | |||

+ | final (Just a@(i,q)) = [a] |
||

+ | final Nothing = [] |
||

+ | </haskell> |
||

+ | |||

+ | which can become a good transformer for list fusion like so: |
||

+ | |||

+ | <haskell> |
||

+ | {-# INLINE encode #-} |
||

+ | encode :: Eq a => [a] -> [(Int,a)] |
||

+ | encode xs = build (\c n -> |
||

+ | let |
||

+ | f x r (Just a@(i,q)) | x == q = r (Just (i+1,q)) |
||

+ | | otherwise = a `c` r (Just (1, x)) |
||

+ | f x r Nothing = r (Just (1, x)) |
||

+ | |||

+ | final (Just a@(i,q)) = a `c` n |
||

+ | final Nothing = n |
||

+ | |||

+ | in |
||

+ | foldr f final xs Nothing) |
||

+ | </haskell> |
||

+ | |||

+ | Just one more way with recursion: |
||

+ | |||

+ | <haskell> |
||

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

+ | encode = let f acc [] = acc |
||

+ | f acc (x:xs) = f ((length x, head x): acc) xs |
||

+ | in reverse . f [] |
||

+ | </haskell> |
||

+ | |||

+ | |||

+ | [[Category:Programming exercise spoilers]] |

## Latest revision as of 03:45, 19 May 2021

(*) 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

```
[(length (x:xs), x) | (x:xs) <- 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 using the slightly more verbose (w.r.t. `(&&&)`

) Applicative combinators:

```
encode :: Eq a => [a] -> [(Int, a)]
encode = map ((,) <$> length <*> head) . pack
```

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 :: Eq a => [a] -> [(Int, a)]
encode xs=zip (map length l) h where
l = (group xs)
h = map head l
```

Or if we ignore the rule that we should use the result of P09,

```
encode :: Eq a => [a] -> [(Int,a)]
encode xs = foldr f final xs Nothing
where
f x r (Just a@(i,q)) | x == q = r (Just (i+1,q))
| otherwise = a : r (Just (1, x))
f x r Nothing = r (Just (1, x))
final (Just a@(i,q)) = [a]
final Nothing = []
```

which can become a good transformer for list fusion like so:

```
{-# INLINE encode #-}
encode :: Eq a => [a] -> [(Int,a)]
encode xs = build (\c n ->
let
f x r (Just a@(i,q)) | x == q = r (Just (i+1,q))
| otherwise = a `c` r (Just (1, x))
f x r Nothing = r (Just (1, x))
final (Just a@(i,q)) = a `c` n
final Nothing = n
in
foldr f final xs Nothing)
```

Just one more way with recursion:

```
encode :: [[t]] -> [(Int, t)]
encode = let f acc [] = acc
f acc (x:xs) = f ((length x, head x): acc) xs
in reverse . f []
```