In this post I want to show how you can implement common list operations: union, intersection, difference and concatenation.
Concatenation is the simplest of them all, because type List already has a function call append that does everything for you.
let concat left right =
List.append left right
The union of two lists is a list containing all the distinct elements from the two original lists. We can implement this operation by concatenating the two lists firsts, and the filtering the distinct elements.
let union left right =
List.append left right |> Seq.distinct |> List.ofSeq
The intersection of two lists is a list containing all the elements of the first list that also appear in the second list. We can implement this by interating through the elements of the first list and checking whether the element appears in the second list. To do this in the shortest possible time, with constant lookup time, we can use a HashSet collection. The result is an O(m+n) complexity instead of O(m*n) if you used brute force.
let intersection (left:list< 'a >) (right:list< 'a >) =
let cache = HashSet< 'a >(right, HashIdentity.Structural)
left |> List.filter (fun n -> cache.Contains n)
The difference of two lists is a list containing all the elements from the first list that are not part of the second list. The implementation of difference is very similar to the implementation of the intersection. All that differs is the lambda used for the filtering.
let difference (left:list< 'a >) (right:list< 'a >) =
let cache = HashSet< 'a >(right, HashIdentity.Structural)
left |> List.filter (fun n -> not (cache.Contains n))
Let’s see all these put to a use:
let main() =
let c = concat [4;3;2;1] [2;3;5]
printfn "%A" c
let u = union [4;3;2;1] [2;3;5]
printfn "%A" u
let i = intersection [4;3;2;2;1] [2;3;5]
printfn "%A" i
let d = difference [4;3;2;1] [2;3;5]
printfn "%A" d
main()
This program yields the following output:
[4; 3; 2; 1; 2; 3; 5] [4; 3; 2; 1; 5] [3; 2; 2] [4; 1]
Notice that these operations work with unsorted lists. You don’t have to sort the lists first to apply them.
In order to use the HashSet, you need to add a reference to the FSharp.PowerPack.dll assembly. This sample was build with F# 1.9.7.8 for Visual Studio 2008.
UPDATE: You can read about similar implementations but using operators on this post by Jason Kikel. He also deals with repetitions, regular expression binding operator and null coalescing binding operator.
