使用文件夹删除重复项

Question

我正在尝试编写我的函数remdps的实现，它删除列表中最近的重复项。例如："aaabbbsscaa"应该变成"absca"。我必须使用foldl。这是我的尝试：

helper :: Eq a => [a] -> a -> [a]
helper [] ele = [ele]
helper newlist ele = if tail newlist /= ele then newlist:ele
    else newlist

remdps :: Eq a => [a] -> [a]
remdps list = foldl helper [] list

main = putStrLn (show (remdps "aabssscdddeaffff"))

以及错误：

4.hs:4:41:
    Could not deduce (a ~ [a])
    from the context (Eq a)
      bound by the type signature for helper :: Eq a => [a] -> a -> [a]
      at 4.hs:2:11-33
      `a' is a rigid type variable bound by
          the type signature for helper :: Eq a => [a] -> a -> [a]
          at 4.hs:2:11
    In the second argument of `(/=)', namely `ele'
    In the expression: tail newlist /= ele
    In the expression:
      if tail newlist /= ele then newlist : ele else newlist

4.hs:4:50:
    Could not deduce (a ~ [a])
    from the context (Eq a)
      bound by the type signature for helper :: Eq a => [a] -> a -> [a]
      at 4.hs:2:11-33
      `a' is a rigid type variable bound by
          the type signature for helper :: Eq a => [a] -> a -> [a]
          at 4.hs:2:11
    In the first argument of `(:)', namely `newlist'
    In the expression: newlist : ele
    In the expression:
      if tail newlist /= ele then newlist : ele else newlist

4.hs:4:58:
    Could not deduce (a ~ [a])
    from the context (Eq a)
      bound by the type signature for helper :: Eq a => [a] -> a -> [a]
      at 4.hs:2:11-33
      `a' is a rigid type variable bound by
          the type signature for helper :: Eq a => [a] -> a -> [a]
          at 4.hs:2:11
    In the second argument of `(:)', namely `ele'
    In the expression: newlist : ele
    In the expression:
      if tail newlist /= ele then newlist : ele else newlist
fish: Unknown command './4'
ghc 4.hs; and ./4

问题总是一样的：)。怎么了？

//编辑

好的，我有一个可以工作的代码。它使用了reverse和++，所以非常难看：)。

helper :: Eq a => [a] -> a -> [a]
helper [] ele = [ele]
helper newlist ele = if head (reverse newlist) /= ele then newlist ++ [ele]
    else newlist

remdps :: Eq a => [a] -> [a]
remdps list = foldl helper [] list

main = putStrLn (show (remdps "aabssscdddeaffff"))

Answer 1

helper的类型注释表明ele是类型a

并执行以下测试( == (Newlist)newlist)，但tail if of type a

如果类型不同，则不能比较两个值。

这不是唯一的错误。

Answer 2

我建议你看看Data.List的文档。特别是对于tail，您会看到类型是[a] -> [a]，所以很明显，它不会像人们想象的那样返回列表的最后一个元素。

如果您希望从列表中获取单个元素(最后一个)，则需要类型为[a] -> a的内容。haskell的能力来自于这样一个事实，即这些信息几乎足以找到正确的函数。

就是Hoogle it!

附注:正如Tinctorius的回答中所提到的，这种方法相当慢

Answer 3

扩展我的第二个评论，虽然这没有回答您提出的问题，但我非常不会使用foldl来做这件事。回到我的计划时代，我会用我的这个宠物kfoldr函数来解决它，我已经把它翻译成了Haskell：

-- |  A special fold that gives you both left and right context at each right
-- fold step.  See the example below.
kfoldr :: (l -> a -> l) -> l -> (l -> a -> r -> r) -> (l -> r) -> [a] -> r
kfoldr advance left combine seedRight [] = seedRight left
kfoldr advance left combine seedRight (x:xs) = combine left x (subfold xs)
where subfold = let newLeft = advance left x 
                in newLeft `seq` kfoldr advance newLeft combine seedRight


removeDuplicates :: Eq a => [a] -> [a]
removeDuplicates = kfoldr advance Nothing step (const [])
    where 
      -- advance is the left context generator, which in this case just 
      -- produces the previous element at each position.
      advance _ x = Just x
      -- step's three arguments in this case are:
      --   (a) the element to the left of current
      --   (b) the current element
      --   (c) the solution for the rest of the list
      step Nothing x xs = x:xs
      step (Just x') x xs
           | x == x' = xs
           | otherwise = x:xs

Haskell的Data.List库有mapAccumL和mapAccumR，它们很相似，但它们是映射而不是折叠。还有密切相关的scanl和scanr，它们可能可以用来实现kfoldr (但我没有费心去尝试)。