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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
