Haskell: Number of matches between two lists of ints?

Question

Say I have two lists of integers:

4 12 24 26 35 41

42 24 4 36 2 26

There are 3 matches between the two lists.

How do I count the number of matches between any two list in Haskell?

Thanks.

Answer 1

If you don't need to take care of multiple elements, the easy way is to calculate the length of the intersection

import Data.List

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

Somewhat more efficient is using Sets as intermediate structures, if you also have an Ord instance:

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

If you need to take care of repetitions, using a Map counting the number of occurrences for each element would be a not too difficult modification.

Answer 2

It's going to be quite painful with lists as you've going to need to go through them all the pairs. Something like this prints out the right answer by forming all pairs where they are equal and then counting the size.

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

It's quite awkward to do it this way from a performance point of view. For large lists you're better off using a set as you can test membership quicker (typically O(lg N), sometimes O(1) ) than you can with a list (O(N)).