# 99 questions/Solutions/8

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

m |
|||

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

Line 26: | Line 26: | ||

<haskell> | <haskell> | ||

− | compress (x : y : | + | compress (x:ys@(y:_)) |

− | compress | + | | x == y = compress ys |

+ | | otherwise = x : compress ys | ||

+ | compress ys = ys | ||

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

Line 45: | Line 47: | ||

<haskell> | <haskell> | ||

compress [] = [] | compress [] = [] | ||

− | compress (x:xs) = | + | compress (x:xs) = x : (compress $ dropWhile (== x) xs) |

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

Line 53: | Line 55: | ||

compress :: Eq a => [a] -> [a] | compress :: Eq a => [a] -> [a] | ||

compress x = foldr (\a b -> if a == (head b) then b else a:b) [last x] x | compress x = foldr (\a b -> if a == (head b) then b else a:b) [last x] x | ||

+ | </haskell> | ||

+ | |||

+ | Wrong solution using foldr | ||

+ | <haskell> | ||

+ | compress :: Eq a => [a] -> [a] | ||

+ | compress xs = foldr (\x acc -> if x `elem` acc then acc else x:acc) [] xs | ||

+ | -- Main> compress [1, 1, 1, 2, 2, 1, 1] | ||

+ | -- [2,1] - must be [1,2,1] | ||

+ | </haskell> | ||

+ | |||

+ | |||

+ | |||

+ | and using foldl | ||

+ | |||

+ | <haskell> | ||

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

+ | compress x = foldl (\a b -> if (last a) == b then a else a ++ [b]) [head x] x | ||

+ | compress' x = reverse $ foldl (\a b -> if (head a) == b then a else b:a) [head x] x | ||

</haskell> | </haskell> |

## Revision as of 09:57, 24 June 2012

(**) Eliminate consecutive duplicates of list elements.

compress :: Eq a => [a] -> [a] compress = map head . group

We simply group equal values together (using Data.List.group), then take the head of each.
Note that (with GHC) we must give an explicit type to *compress* otherwise we get:

Ambiguous type variable `a' in the constraint: `Eq a' arising from use of `group' Possible cause: the monomorphism restriction applied to the following: compress :: [a] -> [a] Probable fix: give these definition(s) an explicit type signature or use -fno-monomorphism-restriction

We can circumvent the monomorphism restriction by writing *compress* this way (See: section 4.5.4 of the report):

compress xs = map head $ group xs

An alternative solution is

compress (x:ys@(y:_)) | x == y = compress ys | otherwise = x : compress ys compress ys = ys

Another possibility using foldr

compress :: (Eq a) => [a] -> [a] compress = foldr skipDups [] where skipDups x [] = [x] skipDups x acc | x == head acc = acc | otherwise = x : acc

A very simple approach:

compress [] = [] compress (x:xs) = x : (compress $ dropWhile (== x) xs)

Another approach, using foldr

compress :: Eq a => [a] -> [a] compress x = foldr (\a b -> if a == (head b) then b else a:b) [last x] x

Wrong solution using foldr

compress :: Eq a => [a] -> [a] compress xs = foldr (\x acc -> if x `elem` acc then acc else x:acc) [] xs -- Main> compress [1, 1, 1, 2, 2, 1, 1] -- [2,1] - must be [1,2,1]

and using foldl

compress :: (Eq a) => [a] -> [a] compress x = foldl (\a b -> if (last a) == b then a else a ++ [b]) [head x] x compress' x = reverse $ foldl (\a b -> if (head a) == b then a else b:a) [head x] x