0

我正在尝试实现一个 Haskell Bag (multiset)。

到目前为止，我有这个

data Bag a = EmptyBag | ListBag [(a, Integer)] deriving (Eq, Show)

emptyBag :: Bag a
emptyBag = EmptyBag

add :: a -> (Bag a) -> (Bag a)
add element EmptyBag = ListBag [(element,1)]
add element (ListBag bag)
  | element `elem` map fst bag = ListBag bag -- will actually increment the count, and return the new bag.

我得到错误

No instance for (Eq a)
      arising from a use of `elem'
    In the expression: element `elem` map fst bag

编译时。这是因为您无法确定两种不同类型的相等性吗？如何确定 Bag 中项目的第一个元素是否已经在 Bag 中？

另外，关于如何实现增加特定项目的计数，并用新的 (element,count) 元组返回包的任何提示？

4

2 回答 2

6

问题的直接原因是并非所有类型都具有可比性。您可以通过更改类型签名将您的类型限制为仅使用提供相等比较的类型：

add :: Eq a => a -> Bag a -> Bag a

您可能想查看 Hackage 上的multiset-comb和data-ordlist包以获取更多实施技巧。

最后一点，我发现EmptyBag构造函数有点可疑：它与例如ListBag []?

于 2012-06-24T06:39:12.927 回答
5

是的，问题是 Haskell 不能比较任意元素的相等性——它只能比较属于类型类的Eq类型。这是有道理的：比较某些事物，比如函数，是无法确定的。其他语言有“引用相等”的概念，但这在 Haskell 中没有意义。所以有些类型的值根本无法比较是否相等。除非您有某种方法可以比较两个值是否相等，否则您无法检查列表中是否已经存在某些内容，这就是Eq提供的。

这意味着任何集合（或多集合）实现都将依赖于Eq（或其他一些显式比较函数）。实际上，Ord出于性能原因，集合往往也依赖于，但由于您只是使用列表，因此不必担心。这也意味着你不能让你的多重集成为 Functor 或 Monad，而是 c'est la vie。

简而言之：您必须将类型限制为Eq. 所以改成a -> Bag a -> Bag g等等Eq a => a -> Bag a -> Bag a。

由于看起来您只是在做一些练习来学习语言（我希望这不会显得居高临下），所以我只会为您的第二个问题提供一些提示。

递归思考。首先，考虑一个基本情况：如何将元素添加到空的多重集中？另一个基本情况：给定一个以你的元素作为列表头部的多重集，你如何创建一个新的、递增的多重集？最后，递归案例：如果您有一个列表，其中头部不是您想要增加的元素，您会怎么做？一旦你回答了所有这些问题，你就可以通过列表中的模式匹配将每个问题写成一个单独的案例，并将它们放在一起以获得你的add功能。

另一个注意事项：拥有EmptyBag构造函数是多余的。列表可能已经为空！有什么ListBag []不同EmptyBag？在这种情况下，我只有一个构造函数。

所以你的 add 函数看起来像这样：

add :: Eq a => a -> Bag a -> Bag a
add x (ListBag []) = ...
add x (ListBag [(x', n)]) = ...

只需填写...适当的案例，就可以了。

根据您的评论，这里有一些示例代码，说明如何在递归时保留列表。

基本上，主要思想很简单：在递归的情况下，不是只返回传递给函数的列表的其余部分，而是返回当前元素，然后是列表的其余部分。基本情况仍然很简单：

add :: Eq a => a -> Bag a -> Bag a
add x (ListBag []) = ListBag [(x, 1)] -- first base case
add x (ListBag (x', n):xs)
  | x == x'   = ListBag $ (x', n + 1) : xs -- second base case
  | otherwise = let ListBag rest = add x (ListBag xs) in ListBag $ (x', n) : rest

您必须使用该let语句将列表从列表中取出，ListBag以便您可以将未触及的元组放回它的前面。

在考虑这样的递归时，我不希望将其视为一系列步骤，而是分别考虑每种情况。在每种情况下，我们都希望返回给定的全部 ListBag内容。所以我们需要将我们正在处理的元组与列表的其余部分结合起来。在递归的情况下，我们从递归调用中获取列表的其余部分；在第二种基本情况下，我们不必再次调用该函数。

因此，通过在每一步返回整个包，我们在所有递归结束时维护整个列表。

我希望这能让它更清楚。

于 2012-06-24T06:41:37.573 回答