Haskell:两个整数列表之间的匹配数量？

Question

假设我有两个整数列表:

4 12 24 26 35 41

42 24 4 36 2 26

两个列表之间有3个匹配项.

如何计算Haskell中任意两个列表之间的匹配数？

谢谢.

Answer 1

如果您不需要处理多个元素,那么简单的方法是计算交叉点的长度

import Data.List

matches :: Eq a => [a] -> [a] -> Int
matches xs ys = length (intersect xs ys)

Set如果你还有一个Ord实例,那么使用s作为中间结构会更有效:

import qualified Data.Set as S

matches :: Ord a => [a] -> [a] -> Int
matches xs ys = S.size (S.intersection (S.fromList xs) (S.fromList ys))

如果你需要注意重复,使用Map计数每个元素的出现次数将是一个不太难修改.

Answer 2

对于列表来说会非常痛苦,因为你需要通过它们完成所有对.像这样的东西通过形成它们相等的所有对来打印出正确答案,然后计算尺寸.

let xs = [1,2,3,4]
let ys = [1,2,3,4]
length [x | x <- xs, y <- ys, x == y]

从性能的角度来看,这样做很尴尬.对于大型列表,您最好使用一个集合,因为您可以更快地测试成员资格(通常为O(lg N),有时为O(1)),而不是列表(O(N)).