[Haskell-cafe] Most elegant funciton for removing adjacent duplicates from a list using foldl and foldr

wren ng thornton wren at freegeek.org
Sun Mar 15 20:17:24 EDT 2009

R J wrote:
> I need to write an implementation using foldl, and a separate implementation using foldr, of a function, "remdups xs", that removes adjacent duplicate items from the list xs.  For example, remdups [1,2,2,3,3,3,1,1]= [1,2,3,1].
> My approach is first to write a direct recursion, as follows:
>    remdups               :: (Eq a) => [a] -> [a]
>    remdups []            =  []
>    remdups (x : [])      =  [x]
>    remdups (x : xx : xs) =  if x == xx then remdups (x : xs) else x : remdups (xx : xs)
> This code works, but it has three cases, not usual two, namely [] and (x : xs).

You should take a look at the page on declaration style vs expression 


At the risk of doing homework, it is always the case that you can 
decompose complex pattern matching into basic pattern matching (which 
for lists means it always has two cases, since list has two 

     remdups []          = ...#1
     remdups (x:[])      = ...#2
     remdups (x:(xx:xs)) = ...#3

== {desugar pattern-matching into case}

     remdups = \a -> case a of
                      []          -> ...#1
                      (x:[])      -> ...#2
                      (x:(xx:xs)) -> ...#3

== {desugar case into case}

     remdups = \a -> case a of
                      []    -> ...#1
                      (x:b) -> case b of
                                []      -> ...#2
                                (xx:xs) -> ...#3

This transformation explicitly gives a name to the second argument of 
the first (:) which is beneficial since it means you don't need to 
allocate a new one that's identical to the old one in order to pass to 
the recursion. For the Then we know x==xx therefore (x:xs) == (xx:xs), 
for the Else we need (xx:xs), in both cases we already have an (xx:xs) 
laying around, namely b.

If you want to give a name like this without manually desugaring the 
case statements yourself, then you can use an as-pattern like (x: 
b@(xx:xs)) which will bind the variable b to the value (xx:xs) just like 

[1] This would not be true if, for example, the language could express 
non-linear terms like in Prolog and other logic languages. Pattern 
matching can still be decomposed in such languages, but they need to 
introduce unification constraints along with the smaller patterns, to 
ensure correctness of the transformation.

Live well,

More information about the Haskell-Cafe mailing list