https://wiki.haskell.org/api.php?action=feedcontributions&user=Swaroop&feedformat=atomHaskellWiki - User contributions [en]2024-03-29T02:11:47ZUser contributionsMediaWiki 1.35.5https://wiki.haskell.org/index.php?title=99_questions/Solutions/8&diff=6346299 questions/Solutions/82020-10-02T15:07:20Z<p>Swaroop: Added a solution</p>
<hr />
<div>(**) Eliminate consecutive duplicates of list elements.<br />
<br />
<haskell><br />
compress :: Eq a => [a] -> [a]<br />
compress = map head . group<br />
</haskell><br />
<br />
We simply group equal values together (using Data.List.group), then take the head of each. <br />
<br />
An alternative solution is<br />
<br />
<haskell><br />
compress (x:ys@(y:_))<br />
| x == y = compress ys<br />
| otherwise = x : compress ys<br />
compress ys = ys<br />
</haskell><br><br />
<br />
A variation of the above using <hask>foldr</hask> (note that GHC erases the <hask>Maybe</hask>s, producing efficient code):<br />
<haskell><br />
compress xs = foldr f (const []) xs Nothing<br />
where<br />
f x r a@(Just q) | x == q = r a<br />
f x r _ = x : r (Just x)<br />
</haskell><br />
<br />
Another possibility using foldr (this one is not so efficient, because it pushes the whole input onto the "stack" before doing anything else):<br />
<br />
<haskell><br />
compress :: (Eq a) => [a] -> [a]<br />
compress = foldr skipDups []<br />
where skipDups x [] = [x]<br />
skipDups x acc<br />
| x == head acc = acc<br />
| otherwise = x : acc<br />
</haskell><br />
<br />
<br />
A similar solution without using <hask>foldr</hask>.<br />
<br />
<haskell><br />
compress :: (Eq a) => [a] -> [a]<br />
compress list = compress_acc list []<br />
where compress_acc [] acc = acc<br />
compress_acc [x] acc = (acc ++ [x])<br />
compress_acc (x:xs) acc<br />
| x == (head xs) = compress_acc xs acc<br />
| otherwise = compress_acc xs (acc ++ [x])<br />
</haskell><br />
<br />
A very simple approach:<br />
<br />
<haskell><br />
compress [] = []<br />
compress (x:xs) = x : (compress $ dropWhile (== x) xs)<br />
</haskell><br />
<br />
Another approach, using foldr<br />
<br />
<haskell><br />
compress :: Eq a => [a] -> [a]<br />
compress x = foldr (\a b -> if a == (head b) then b else a:b) [last x] x<br />
</haskell><br />
<br />
Wrong solution using foldr<br />
<haskell><br />
compress :: Eq a => [a] -> [a]<br />
compress xs = foldr (\x acc -> if x `elem` acc then acc else x:acc) [] xs<br />
-- Main> compress [1, 1, 1, 2, 2, 1, 1]<br />
-- [2,1] - must be [1,2,1]<br />
</haskell><br />
<br />
<br />
and using foldl<br />
<br />
<haskell><br />
compress :: (Eq a) => [a] -> [a]<br />
compress x = foldl (\a b -> if (last a) == b then a else a ++ [b]) [head x] x<br />
compress' x = reverse $ foldl (\a b -> if (head a) == b then a else b:a) [head x] x<br />
</haskell><br />
<br />
A crazy variation that acts as a good transformer for fold/build fusion<br />
<br />
<haskell><br />
{-# INLINE compress #-}<br />
compress :: Eq a => [a] -> [a]<br />
compress xs = build (\c n -><br />
let<br />
f x r a@(Just q) | x == q = r a<br />
f x r _ = x `c` r (Just x)<br />
in<br />
foldr f (const n) xs Nothing)<br />
</haskell><br />
<br />
<br />
A simple approach that pairs each element with its consecutive element. We ignore all pairs with the same element, and return the list of all 'firsts' of these pairs. The last element has to be appended at the end.<br />
<br />
<haskell><br />
consecutivePairs a = zip (init a) (tail a)<br />
compress a = [ fst x | x <- consecutivePairs a, (fst x /= snd x) ] ++ [last a]<br />
</haskell><br />
<br><br />
[[Category:Programming exercise spoilers]]</div>Swaroop