0

我正在尝试编写 , 函数的实现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

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

//编辑

好的，我有一个工作代码。它使用reverseand ++，所以非常难看:)。

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"))
4

4 回答 4

2

你可能想要做的是：

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

变化：

  • :仅以一种方式起作用：左侧是列表的头部（type a），右侧是尾部（type [a]）。它有时也被称为“缺点”。你想要做的叫做“snoc”：它的右边是列表的最后一个元素（type a），左边是初始部分（type [a]）。

    Prelude 中不存在“snoc”，因此，您只需以不同的方式编写它：newlist ++ [ele]. （将此与 进行比较x : xs == [x] ++ xs。）

  • tail newlist == ele变成last newlist == ele. tail获取没有头部的列表，但您想比较newlist. 为此，您拥有last. （顺便说一句，要获取列表的初始部分，您可以使用init。）

请注意，您还交换了 if 语句的分支，aaa将答案留给您。-edit- 我看到你现在已经更新了；）

另请注意，这是一种非常缓慢的方法。last随着答案的增长，每个“snoc”都会花费更长的时间remdps，因为 Prelude 列表在“cons”和head. 尝试重写该函数，使其改用“cons”。提示：你会reverse在某个时候需要。

此外，由于工作方式的原因，此函数在与无限列表一起使用时将不起作用foldl。重写这个函数来foldr代替使用可能是一个有趣的练习。

于 2013-01-09T01:16:55.413 回答
1

helper 的类型注释表明 ele属于a 类型
并且您执行以下测试(tail(newlist) == ele)，但 tail if 属于[a] 类型

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

这不是唯一的错误。

于 2013-01-09T01:05:04.880 回答
1

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

如果您想从列表（最后一个）中获取单个元素，则需要带有 type 的东西[a] -> a。haskell 的强大之处在于这些信息几乎足以找到正确的功能。

就胡歌吧！

PS 作为旁注 - 这种方法很慢，正如 Tinctorius 的回答中提到的那样

于 2013-01-09T01:19:47.420 回答
1

为了扩展我的第二条评论，虽然这不能回答你提出的问题，但我不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相似，但它们映射而不是折叠。还有密切相关的scanland scanr，可能可以用来实现kfoldr（但我懒得尝试）。

于 2013-01-09T01:24:54.730 回答