haskell 中的列表中的 Ord 运算符是否存在差异？

Question

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

因此如果有 [1,2,1,4,3] [1,2,4]，则差异为 [1,3]

目前我可以通过正常的 \ 运算符 listA \ listB.

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

我知道 Data.Multiset 模块，它可以更快地执行此操作，但是有没有本地方法可以在没有 Data.Multiset 模块的情况下在列表上执行此操作？

Answer 1

As integers are in ord group it can be done faster.

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

Answer 2

因为我无法使用 Data.MultiSet 我需要通过列表实现我自己的解决方案，所以我将 post 解决方案。

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

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

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

haskell 中的列表中的 Ord 运算符是否存在差异？

Is there a difference Ord operator on lists in haskell?

haskell

set-difference