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 s в качестве промежуточных структур, еслиу вас также есть Ord экземпляр:

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)).

Answer 3

Функция intersect из Data.List возвращает пересечение между двумя заданными списками.

import Data.List (intersect)

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

main = do
    print $ numberOfIntersections [4, 12, 24, 26, 35, 41] [42, 24, 4, 36, 2, 26]

Answer 4

Если вам нужно решение, использующее только списки, которое не так медленно, как Data.List.intersect, вы можете использовать это:

intersectSorted [] _ = []
intersectSorted _ [] = []
intersectSorted (x : xs) (y : ys) = case compare x y of
  LT -> intersectSorted xs (y : ys)
  EQ -> x : intersectSorted xs ys
  GT -> intersectSorted (x : xs) ys

intersect a b = intersectSorted (sort a) (sort b)