Personal tools

99 questions/Solutions/8

From HaskellWiki

< 99 questions | Solutions(Difference between revisions)
Jump to: navigation, search
m
 
(13 intermediate revisions by 9 users not shown)
Line 26: Line 26:
   
 
<haskell>
 
<haskell>
compress (x : y : xs) = (if x == y then [] else [x]) ++ compress (y : xs)
+
compress (x:ys@(y:_))
compress x = x
+
| x == y = compress ys
  +
| otherwise = x : compress ys
  +
compress ys = ys
 
</haskell>
 
</haskell>
   
Line 45: Line 45:
 
<haskell>
 
<haskell>
 
compress [] = []
 
compress [] = []
compress (x:xs) = [x] ++ (compress $ dropWhile (== x) xs)
+
compress (x:xs) = x : (compress $ dropWhile (== x) xs)
  +
</haskell>
  +
  +
Another approach, using foldr
  +
  +
<haskell>
  +
compress :: Eq a => [a] -> [a]
  +
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>

Latest 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