haskell - 如何在无偏见地处理重复项的同时获得列表的交集？

Question

我在标题中的解释可能相当糟糕，但我遇到的问题是:

shared [[10,5,10,10,7,10],[2,6,10,10]]
output: [10,10,10,10]

我希望输出为 [10,10]。

我正在尝试编写 Data.List.intersect 的变体就参数的顺序而言，这是无偏见的。每个值在结果中出现的次数应该相同，无论它在哪个列表中出现的次数更少。 (相比之下，对于 Data.List.intersect，如果一个值出现在结果中，它出现的次数将与第一个列表中的相同。)

我目前的尝试是:

import Data.List
myintersect :: Eq a => [a] -> [a] -> [a]
myintersect [] _ = []
myintersect (x:xs) ys
    | x `elem` ys = x : myintersect xs ys
    | otherwise = myintersect xs ys

shared :: (Eq a) => [[a]] -> [a]
shared x = foldr1 myintersect x

虽然它不能正常工作。 共享 [[10,5,10,10,7,10],[2,6,10,10]] 是 [10,10,10,10] ，而不是 [10,10]。

我一直在研究使用 zip，但它无法处理不同长度的列表。

Answer 1

我建议你先对列表进行排序，然后并排遍历它们:

shared xs ys = go xs' ys' where
  go [] _ = []
  go _ [] = []
  go aas@(a:as) bbs@(b:bs) = case compare a b of
    GT -> go aas bs
    EQ -> a : go as bs
    LT -> go as bbs
  xs' = sort xs
  ys' = sort ys

正如@WillNess 在评论中指出的那样，Data.List.Ordered 有 just the function you want :

isect :: Ord a => [a] -> [a] -> [a]
-- |  The 'isect' function computes the intersection of two ordered lists.
-- An element occurs in the output as many times as the minimum number of
-- occurrences in either input.  If either input is a set,  then the output
-- is a set.
--
-- > isect [ 1,2, 3,4 ] [ 3,4, 5,6 ]   == [ 3,4 ]
-- > isect [ 1, 2,2,2 ] [ 1,1,1, 2,2 ] == [ 1, 2,2 ]

由于 Data.List.Ordered 中的函数假定输入列表已排序，因此您必须 sort他们 first :

import Data.Function (on)
import Data.List     (sort)

bettershared = Data.List.Ordered.isect `on` sort