F# Operations on List

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

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

7 Replies to “F# Operations on List”

  1. Hi there, You’ve done a fantastic job. I will definitely digg it and personally suggest to my friends. I have bookmarked it in my web and social networks. I am sure they’ll be benefited from this site.

  2. Just wish to say your article is as surprising. The clarity in your post is simply nice and i can assume you’re an expert on this subject. Well with your permission allow me to grab your RSS feed to keep up to date with forthcoming post, bookmarked it in my blog and google bookmarks.. Thanks a million and please continue the enjoyable work.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.