Personal tools

99 questions/Solutions/8

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
m (Pointed to the correct module in which group is defined)
(Adding another potential solution using foldr)
Line 29: Line 29:
 
compress [a] = [a]
 
compress [a] = [a]
 
compress (x : y : xs) = (if x == y then [] else [x]) ++ compress (y : xs)
 
compress (x : y : xs) = (if x == y then [] else [x]) ++ compress (y : xs)
  +
</haskell>
  +
  +
Another possibility using foldr
  +
  +
<haskell>
  +
compress :: (Eq a) => [a] -> [a]
  +
compress = foldr skipDups []
  +
where skipDups x [] = [x]
  +
skipDups x acc
  +
| x == head acc = acc
  +
| otherwise = x : acc
 
</haskell>
 
</haskell>

Revision as of 17:05, 27 July 2010

(**) 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 [] = []
compress [a] = [a]
compress (x : y : xs) = (if x == y then [] else [x]) ++ compress (y : xs)

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