haskell - 在haskell中的列表上是否有不同的Ord运算符？

Question

我想在 2 个整数列表之间设置差异，这允许在 haskell 中重复。

所以在有的情况下[1,2,1,4,3] [1,2,4]，区别是[1,3]

目前我可以通过普通\\操作员来完成listA \\ listB。

但问题是这太慢了。由于整数在 ord 组中，因此可以更快地完成。

我知道该Data.Multiset模块，它会做得更快，但是有没有一种本地方法可以在没有Data.Multiset模块的列表上执行它？

Answer 1

由于整数在 ord 组中，因此可以更快地完成。

是的，但它需要建立一个排序索引。这就是Data.Multiset正在做的事情。您当然可以编写一个手动执行该操作的操作，但到那时您将有效地重新实现Multiset。

Answer 2

由于我无法使用Data.MultiSet，我需要通过列表来实现我自己的解决方案，所以我将发布解决方案。

为了得到有重复的两个列表的集合差异，我们首先需要将数字组合在一起，以获得每个数字的重复次数：

tupleGroup [] _ = []
tupleGroup (hd:tl) (x, y) 
  | hd == x = (x, succ y) : tupleGroup tl (x, succ y)
  | otherwise = (hd, 1) : tupleGroup tl (hd, 1)

group' [] = []
group' (hd:tl) = tupleGroup tl (hd, 1) 

为了调用辅助函数 group' 我们首先需要对列表进行排序，因为 tupleGroup 需要一个排序列表。

下一个函数是差分函数，我们在其中提供分组列表：

difference [] [] = []
difference (hd:tl)  [] = fst hd : difference tl []
difference [] (hd:tl) = []
difference (hd1:tl1) (hd2:tl2) 
  | x1 == x2 && y1 > y2 = x1 : difference tl1 tl2
  | x1 == x2 = difference tl1 tl2
  | x1 < x2 = x1 : difference tl1 (hd2:tl2)
  | otherwise = difference (hd1:tl1) tl2
  where 
    x1 = fst hd1
    x2 = fst hd2
    y1 = snd hd1
    y2 = snd hd2

该函数将返回所有数字的列表，第一个列表中的重复计数大于第二个列表中的重复次数。