F# supports a powerful implementation of immutable lists (see Dustin’s introduction). But for my current work I needed a sorted list and of course I wanted it the F#-way, which means immutable. I didn’t want to reinvent the wheel so I asked my question in the hubFS forum.

It turned out (thanks to Robert) that F# uses red-black trees to give a fast implementation for the immutable set. This means that a set in F# stores all elements in a *balanced binary tree* and searching for an element costs only *O(log n)*. As a side effect all elements can be visited in the underlying order, which means the set implementation gives a possibility for implementing a sorted list. The only limitation is that a set usually don’t store objects more than once.

The next problem I got, was that my sorted list needs a specific ordering function. The standard F# set implementation uses structural comparison to give an order, which is not the order I need. But Laurent mentioned the *Set.Make* function in the F# PowerPack. This function creates a new set type for the given ordering function. The only problem with Set.Make is that it was only designed for OCaml compatibility. But with this hint I was able to put all information together and got a nice immutable sorted list implementation for F#:

// wrap orderingFunction as Collections.Generic.IComparer type 'a FComparer = {compareF: 'a -> 'a -> int} static member Create(compareF) = {new 'a FComparer with compareF = compareF} interface Collections.Generic.IComparer<'a> with member x.Compare(a, b) = x.compareF a b

// a immutable sorted list - based on F# set type 'a SortedFList = {items: Tagged.Set<'a,Collections.Generic.IComparer<'a>> } member x.Min = x.items.MinimumElement member x.Items = seq {for item in x.items do yield item} member x.Length = x.items.Count member x.IsEmpty = x.items.IsEmpty static member FromList(list, sortFunction) = let comparer = FComparer<'a>.Create(sortFunction) {new 'a SortedFList with items = Tagged.Set<'a>.Create(comparer,list)} static member FromListWithDefaultComparer(list) = SortedFList<'a>.FromList(list,compare) static member Empty(sortFunction) = SortedFList<'a>.FromList([],sortFunction) static member EmptyWithDefaultComparer() = SortedFList<'a>.Empty(compare) member x.Add(y) = {x with items = x.items.Add(y)}

member x.Remove(y) = {x with items = x.items.Remove(y)}

Please note that this implementation stores every item only once. Next time I will show a version which allows to store repeated items.

Tags: F#, immutable sorted list, red-black trees, immutable set