# 99 questions/Solutions/10

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

m (Added note on MR) |
|||

(8 intermediate revisions by 6 users not shown) | |||

Line 13: | Line 13: | ||

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

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

<haskell> |
<haskell> |
||

Line 25: | Line 25: | ||

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> |
||

+ | |||

+ | Or with the help of foldr (''pack'' is the resulting function from P09): |
||

+ | |||

+ | <haskell> |
||

+ | encode xs = (enc . pack) xs |
||

+ | where enc = foldr (\x acc -> (length x, head x) : acc) [] |
||

+ | </haskell> |
||

+ | |||

+ | Or using takeWhile and dropWhile: |
||

+ | |||

+ | <haskell> |
||

+ | encode [] = [] |
||

+ | encode (x:xs) = (length $ x : takeWhile (==x) xs, x) |
||

+ | : encode (dropWhile (==x) xs) |
||

+ | </haskell> |
||

+ | |||

+ | Or without higher order functions: |
||

+ | |||

+ | <haskell> |
||

+ | 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 |
||

+ | </haskell> |
||

+ | |||

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

+ | |||

+ | <haskell> |
||

+ | import List |
||

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

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

+ | l = (group xs) |
||

+ | h = map head l |
||

</haskell> |
</haskell> |

## Revision as of 11:23, 26 July 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

(&&&)

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