haskell - Haskell Bag(多集)实现

Question

我正在尝试实现Haskell Bag(多集)。

到目前为止，我已经有了

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 []有何不同？