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