Haskell: ¿Número de coincidencias entre dos listas de entradas?

Question

Decir que tengo dos listas de números enteros:

4 12 24 26 35 41 

42 24 4 36 2 26 

hay 3 partidos entre las dos listas.

¿Cómo cuento el número de coincidencias entre dos listas en Haskell?

Gracias.

Answer 1

Si no es necesario para cuidar de múltiples elementos, el camino más fácil es calcular la longitud de la intersección

import Data.List 

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

Algo más eficiente es el uso de Set s como estructuras intermedias, si también tiene Ord un ejemplo:

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

Si tiene que cuidar de repeticiones, utilizando un Map contar el número de veces que ocurrió cada elemento sería una modificación no es demasiado difícil.

Answer 2

Va a ser muy doloroso con las listas, ya que tendrá que pasar por todas las parejas. Algo así imprime la respuesta correcta al formar todos los pares donde son iguales y luego contar el tamaño.

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

Es bastante incómodo hacerlo de esta manera desde un punto de vista del rendimiento. Para listas grandes, es mejor utilizar un conjunto ya que puede probar la membresía más rápido (normalmente O (lg N), a veces O (1)) que con una lista (O (N)).

Answer 3

La función intersect de Data.List devuelve la intersección entre dos listas dadas.

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

Si desea una solución utilizando sólo las listas, que no es tan lento como Data.List.intersect, puede utilizar esto:

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)