Haskell: Liczba dopasowań między dwiema listami ints?

Question

Powiedz, mam dwie listy liczb całkowitych:

4 12 24 26 35 41 

42 24 4 36 2 26 

Istnieją 3 mecze pomiędzy tymi dwoma listami.

Jak policzyć liczbę dopasowań między dowolnymi dwoma listami w Haskell?

Dzięki.

Answer 1

Jeśli nie trzeba dbać o wielu elementach, w łatwy sposób to obliczyć długość przecięcia

import Data.List 

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

Nieco bardziej skuteczny jest przy użyciu Set S, jako struktur pośrednich, jeśli masz również Ord instancja:

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

Jeśli trzeba dbać o powtórzeniach, przy użyciu Map licząc liczbę wystąpień dla każdego elementu nie byłoby zbyt trudne modyfikacji.

Answer 2

To będzie bardzo bolesne z listami, ponieważ będziesz musiał przejść przez nie wszystkie pary. Coś takiego wypisuje właściwą odpowiedź, tworząc wszystkie pary, w których są one równe, a następnie licząc rozmiar.

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

To dość niewygodne, aby zrobić to w ten sposób z punktu widzenia wydajności. W przypadku dużych list lepiej jest używać zestawu, ponieważ możesz szybciej przetestować członkostwo (zwykle O (lg N), czasami O (1)) niż na liście (O (N)).

Answer 3

Funkcja intersect z Data.List zwraca przecięcie dwóch podanych 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

Jeśli chcesz rozwiązanie przy użyciu tylko list, który nie jest tak powolne jak Data.List.intersect, można użyć tego:

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)