Haskell Bag (Multiset)实现

Question

我正在尝试实现一个Haskell包(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

编译时。这是因为你不能确定两个不同类型的相等吗？如何确定袋子中物品的第一个元素是否已经在袋子中？

另外，关于如何实现递增特定项的计数，并返回包含新的(element，count)元组的包，有什么建议吗？

Answer 1

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

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

您可能希望查看Hackage上的multiset-comb和data-ordlist包，以获得进一步的实现技巧。

最后，我发现EmptyBag构造函数有点可疑:它与ListBag []有什么不同

Answer 2

是的，问题是Haskell不能比较任意元素是否相等--它只能比较属于Eq类型类的类型。这是有道理的:比较某些东西，比如函数，是无法确定的。其他语言有“引用相等”的概念，但这在Haskell中没有意义。因此，有些类型的值从根本上是不能进行相等比较的。你不能检查某个东西是否已经在列表中，除非你有方法比较两个值是否相等，这就是Eq所提供的。

这意味着任何set (或multiset)实现都将依赖于Eq (或其他显式比较函数)。在实践中，出于性能原因，sets往往也依赖于Ord，但由于您只使用列表，所以不必担心。这也意味着你不能使你的多集函数或Monad，但c‘’est la vie。

简而言之:您必须将您的类型限制为Eq。因此，将a -> Bag a -> Bag g更改为Eq a => a -> Bag a -> Bag a，依此类推。

既然看起来你只是在做一些练习来学习这门语言(我希望这不会给人以居高临下的印象)，我就给你一些提示来回答你的第二个问题。

递归地思考。首先，考虑一个基本情况:如何将元素添加到一个空的多集？另一种基本情况:给定一个元素作为列表头部的多集，如何创建一个新的、递增的多集？最后，递归情况:如果有一个列表，其中head不是您想要递增的元素，该怎么办？一旦您回答了所有这些问题，您就可以在列表中按模式匹配地将每个问题编写为一个单独的案例，然后将它们放在一起以获得您的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。因此，我们需要将我们正在处理的元组与列表的其余部分进行cons。在递归情况下，我们从递归调用中获得列表的其余部分；在第二种基本情况下，我们不必再次调用函数。

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

我希望这能让事情变得更清楚。