Haskell Bag(Multiset)实现

Question

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

编译时 这是因为你无法确定两种不同类型的平等吗？如何确定包中物品的第一个元素是否已经放入包中？

此外,有关如何实现递增特定项的计数,并使用新的(元素,计数)元组返回包的任何提示？

Answer 1

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

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

您可能需要查看Hackage上的multiset-comb和data-ordlist包,以获取进一步的实施技巧.

作为最后一点,我发现EmptyBag构造函数有点怀疑:它与例如,它有什么不同ListBag []？

Answer 2

是的，问题是 Haskell 不能比较任意元素的相等性——它只能比较属于Eqtypeclass 的类型。这是有道理的：比较某些东西，比如函数，是无法确定的。其他语言有“引用相等”的概念，但这在 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。所以我们需要使用列表的其余部分来处理我们正在处理的元组。在递归情况下，我们从递归调用中获取列表的其余部分；在第二种基本情况下，我们不必再次调用该函数。

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

我希望这能让它更清楚。