Geek Answers Handbook

Haskell: Number of matches between two ints lists?

Let's 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 to count the number of matches between any two lists in Haskell?

Thank.

+5
source share
4 answers

If you don’t need to care about multiple elements, an 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 use Setas intermediate structures if you also have an instance 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))

If you need to take care of repetitions, using Mapcounting the number of occurrences for each element will not be a very complicated modification.

+11

, . - , , , .

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

+6

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]
+2

, , , 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)
+1

More articles:


All Articles