F# Seq diff

14
votes

given two sequences, how to get all the elements belonging to both the sequences or all the elements unique to one of them?

Example:

let a = [1..10]
let b = [3; 5; 7]

How do I compute 3 5 and 7 (all the elements common to both the list) and 1, 2, 4, 6, 8, 9, 10 (all the elements not in common)

Thanks

3
f#
Can you give an example? - Dario

3 Answers

13
votes

What you want to do is no more than the simple set operations of intersection and difference (or relative complement).

F# has the Set module to help us out here. This should do the job:

let a = [1 .. 10]
let b = [3; 5; 7]

let intersection = Set.intersect (Set.ofList a) (Set.ofList b)
let difference = (Set.ofList a) - (Set.ofList b)

You can then of course convert back the results into lists using Set.toList, if you wish.

As Mehrdad points out, this can be done alternatively using LINQ (or even the HashSet class in the BCL), but the approach here would seem to be most in the spirit of the F# language (certainly the nicest syntactically, and probably the most efficient too).

9
votes

Slightly more compact:

let a = set [0;1;2;3]
let b = set [2;3;4;5]
let c = a - b
let d = b - a
let e = Set.intersect a b
let f = a + b
> 
val c : Set<int> = seq [0; 1]
val d : Set<int> = seq [4; 5]
val e : Set<int> = seq [2; 3]
val f : Set<int> = seq [0; 1; 2; 3; ...]

Danny

5
votes

Not very F#-y way I know of. You can always resort to .NET libraries. seq<T> is just IEnumerable<T>, nothing special:

let diff = System.Linq.Enumerable.Except(seq1, seq2); // seq1 - seq2
let intersect = System.Linq.Enumerable.Intersect(seq1, seq2);
let symdiff = System.Linq.Enumerable.Union(System.Linq.Enumerable.Except(seq1, seq2), System.Linq.Enumerable.Except(seq2, seq1));