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

[wren ng thornton]

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 
style:

     http://haskell.org/haskellwiki/Declaration_vs._expression_style

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 
constructors).[1]

     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 
above.


[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,
~wren