[F#] Common Intersection of a sequence of sequences

The idea is to find the common intersection of a sequence of sequences — or lists or arrays (in red in the image below).

Intersection of 3 sets

Intersection of 3 sets

Let’s say we have a bunch of CSV files and we want to find all the common columns between these files.

We are goint to use the following data for testing:

let headersByFile = seq{
    yield [ "id"; "name"; "date"; "color" ]
    yield [ "id"; "age"; "date" ]
    yield [ "id"; "sex"; "date"; "animal" ]
}
// val headersByFile : seq<string list>

And we want to have as result:

[ "id"; "date" ]

As the Intersection operation is associative:

(A ∩ B) ∩ C = A ∩ (B ∩ C)

We can compute the intersection of the first list and the second list and then use the result to compute the intersection with the third list and so on.

That sounds like a familiar high order function: Seq.reduce.

In F# we don’t have a built-in function to compute the intersection of two lists or sequences — as we do in C# with Enumerable.Intersect — but we do have an intersection function in the Set module to work with sets, so we will use it.

First we need to transform our sequence of lists in a sequence of sets (working directly with our data):


let headersByFileSet = Seq.map Set.ofList headersByFile
// val headersByFileSet : seq<Set<string>>

We have now a sequence of sets in which we can apply a ‘reduction’ using the Set.intersect function.


let commonHeaders = Seq.reduce Set.intersect headersByFileSet 
// val commonHeaders : Set<string> = set ["date"; "id"]

And that is all!

A way to gather all this together is using the ‘pipeline‘ operator:

let commonHeaders = 
      headersByFile
      |> Seq.map Set.ofList
      |> Seq.reduce Set.intersect
// val commonHeaders : Set<string> = set ["date"; "id"]

Or making even a generic function using ‘function composition‘ and ‘function partial application‘:

let commonIntersection = Seq.map Set.ofList >> Seq.reduce Set.intersect
// val commonIntersection : (seq<string list> -> Set<string>)

let commonHeaders = commonIntersection  headersByFileSet 
// val commonHeaders : Set<string> = set ["date"; "id"]

[Update]
There is built-in function in the Set module to calculate directly the common intersection of a sequence of sets: Set.intersectMany, so we only need to transform our sequence of lists to a sequence of sets.

let commonHeaders = 
      headersByFile
      |> Seq.map Set.ofList
      |> Set.intersectMany
// val commonHeaders : Set<string> = set ["date"; "id"]