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

From HaskellWiki

< 99 questions | Solutions

(Added new solution for problem 8 using foldr) |
|||

Line 57: | Line 57: | ||

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

− | + | Wrong solution using foldr | |

<haskell> | <haskell> | ||

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

compress xs = foldr (\x acc -> if x `elem` acc then acc else x:acc) [] xs | 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> | </haskell> | ||

Line 71: | Line 72: | ||

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

compress x = foldl (\a b -> if (last a) == b then a else a ++ [b]) [head x] x | 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
```