Haskell实现：移除列表中相邻重复元素的问题求助

Hey there! It looks like you're tackling a Haskell problem that goes beyond just removing one set of adjacent duplicates—you need to keep eliminating pairs until no adjacent duplicates are left, since your examples show removing pairs can create new duplicates that also need handling (like turning "abbac" into "c", not stopping at "aac").

Your initial idea of removing the first adjacent duplicate and reprocessing the list is totally valid, but we can make this more efficient with a stack-based approach that handles everything in a single pass. Let’s break this down step by step.

Clarify the Problem Requirements #

From your examples, here’s what we need the function to do:

• Input: "acvvca" → Output: "" (remove "vv" → "acca", remove "cc" → "aa", remove "aa" → empty)
• Input: "1456776541" → Output: "" (remove "77" → "14566541", remove "66" → "145541", remove "55" → "1441", remove "44" → "11", remove "11" → empty)
• Input: "abbac" → Output: "c" (remove "bb" → "aac", remove "aa" → "c")
• Input: "aabaabckllm" → Output: "ckm" (remove pairs step-by-step until only "ckm" remains)

The Stack-Based Approach (Efficient & Idiomatic) #

Instead of repeatedly scanning the list to find the first duplicate pair, we can build the result using a stack (a list acting as a stack) as we iterate through the input. For each element:

1. If the stack isn’t empty and the top element matches the current element, pop the top (we remove this pair).
2. If the stack is empty or the top element is different, push the current element onto the stack.

This handles new duplicates created by previous removals immediately, no need to re-scan the whole list.

Complete Implementation #

module Test where

removeAdjDups :: (Eq a) => [a] -> [a]
removeAdjDups = reverse . foldl processElement []
  where
    processElement stack x
      | not (null stack) && head stack == x = tail stack  -- Pop the duplicate pair
      | otherwise = x : stack                             -- Push the new element

How It Works

• We use foldl to iterate through the input, building our stack.
• Since we prepend elements to the stack, we reverse the final stack to get the correct order.
• Testing with your examples:
  • removeAdjDups "abbac" → ends with stack [c], reversed to "c" ✔️
  • removeAdjDups "aabaabckllm" → ends with stack [m,k,c], reversed to "ckm" ✔️

Sticking to Your Initial Recursive Idea #

If you’d prefer to implement your original approach (find the first pair, remove it, then reprocess the entire list), here’s a working version. Note this is less efficient for long lists (multiple full scans), but it’s a straightforward way to model the problem:

module Test where

removeAdjDups :: (Eq a) => [a] -> [a]
removeAdjDups lst = case findAndRemoveFirstPair lst of
  Nothing -> lst  -- No pairs left, return the list
  Just newLst -> removeAdjDups newLst  -- Re-process the updated list

-- Helper to find the first adjacent pair and remove it
findAndRemoveFirstPair :: (Eq a) => [a] -> Maybe [a]
findAndRemoveFirstPair [] = Nothing
findAndRemoveFirstPair [x] = Nothing
findAndRemoveFirstPair (x:y:rest)
  | x == y = Just rest  -- Remove x and y, return the remaining elements
  | otherwise = (x :) <$> findAndRemoveFirstPair (y:rest)  -- Keep x, check the rest

This works by repeatedly removing the first pair and re-running the function until no pairs are left—matching all your expected outputs.

Final Notes #

• The stack-based method is the idiomatic Haskell solution—it’s efficient (linear time) and uses common higher-order functions like foldl.
• Both approaches are valid, but the stack method is preferred for larger datasets.
• Test with all your examples to confirm correctness!

内容的提问来源于stack exchange，提问作者user6306428