CODEWITHSUNDEEP
listhaskellrecursionfold
user6306428
user6306428

Reputation:

Haskell - Removing adjacent duplicates from a list

I'm trying to learn haskell by solving some online problems and training exercises.

Right now I'm trying to make a function that'd remove adjacent duplicates from a list.

Sample Input

"acvvca"

"1456776541"

"abbac"

"aabaabckllm"

Expected Output

""

""

"c"

"ckm"

My first though was to make a function that'd simply remove first instance of adjacent duplicates and restore the list.

module Test where

removeAdjDups :: (Eq a) => [a] -> [a]
removeAdjDups []           =  []
removeAdjDups [x]          =  [x]
removeAdjDups (x : y : ys)
  | x == y = removeAdjDups ys
  | otherwise = x : removeAdjDups (y : ys)

*Test> removeAdjDups "1233213443"
"122133"

This func works for first found pairs.

So now I need to apply same function over the result of the function.

Something I think foldl can help with but I don't know how I'd go about implementing it.

Something along the line of

removeAdjDups' xs = foldl (\acc x -> removeAdjDups x acc) xs

Also is this approach the best way to implement the solution or is there a better way I should be thinking of?

Upvotes: 1

Views: 2318

Answers (4)

jferard
jferard

Reputation: 8180

I don't see either how to use foldl. It's maybe because, if you want to fold something here, you have to use foldr. 

main = mapM_ (print . squeeze) ["acvvca", "1456776541", "abbac", "aabaabckllm"]

-- I like the name in @bipll answer
squeeze = foldr (\ x xs -> if xs /= "" && x == head(xs) then tail(xs) else x:xs) ""

Let's analyze this. The idea is taken from @bipll answer: go from right to left. If f is the lambda function, then by definition of foldr:

squeeze "abbac" = f('a' f('b' f('b' f('a' f('c' "")))

By definition of f, f('c' "") = 'c':"" = "c" since xs == "". Next char from the right: f('a' "c") = 'a':"c" = "ac" since 'a' != head("c") = 'c'. f('b' "ac") = "bac" for the same reason. But f('b' "bac") = tail("bac") = "ac" because 'b' == head("bac"). And so forth...

Bonus: by replacing foldr with scanr, you can see the whole process:

Prelude> squeeze' = scanr (\ x xs -> if xs /= "" && x == head(xs) then tail(xs) else x:xs) ""
Prelude> zip "abbac" (squeeze' "abbac")
[('a',"c"),('b',"ac"),('b',"bac"),('a',"ac"),('c',"c")]

Upvotes: 0

fp_mora
fp_mora

Reputation: 714

List comprehensions are often overlooked. They are, of course syntactic sugar but some, like me are addicted. First off, strings are lists as they are. This functions could handle any list, too as well as singletons and empty lists. You can us map to process many lists in a list.

(\l -> [ x  | (x,y) <- zip l $ (tail l) ++ " ", x /= y]) "abcddeeffa"

"abcdefa"

Upvotes: 1

leftaroundabout
leftaroundabout

Reputation: 120711

I don't see how foldl could be used for this. (Generally, foldl pretty much combines the disadvantages of foldr and foldl'... those, or foldMap, are the folds you should normally be using, not foldl.)

What you seem to intend is: repeating the removeAdjDups, until no duplicates are found anymore. The repetition is a job for

iterate :: (a -> a) -> a -> [a]

like

Prelude> iterate removeAdjDups "1233213443"
["1233213443","122133","11","","","","","","","","","","","","","","","","","","","","","","","","","","",""...

This is an infinite list of ever reduced lists. Generally, it will not converge to the empty list; you'll want to add some termination condition. If you want to remove as many dups as necessary, that's the fixpoint; it can be found in a very similar way to how you implemented removeAdjDups: compare neighbor elements, just this time in the list of reductions.

bipll's suggestion to handle recursive duplicates is much better though, it avoids unnecessary comparisons and traversing the start of the list over and over.

Upvotes: 2

bipll
bipll

Reputation: 11940

Start in last-first order: first remove duplicates from the tail, then check if head of the input equals to head of the tail result (which, by this moment, won't have any duplicates, so the only possible pair is head of the input vs. head of the tail result):

main = mapM_ (print . squeeze) ["acvvca", "1456776541", "abbac", "aabaabckllm"]

squeeze :: Eq a => [a] -> [a]
squeeze (x:xs) = let ys = squeeze xs in case ys of
                                            (y:ys') | x == y -> ys'
                                            _ -> x:ys
squeeze _ = []

Outputs

""
""
"c"
"ckm"

Upvotes: 3

Related Questions