Last time I showed how the immutable set implementation in F# can be used to get a immutable sorted list. As a result of using sets, the shown version doesn’t support repeated items. This lack can be wiped out by using an additional dictionary (immutable "Map" in F#) which stores the count of each item.

At first I define two basic helper functions for the dictionary:

module MapHelper =
let addToMap map idx =
let value = Map.tryfind idx map
match value with
| Some(x) -> Map.add idx (x+1) map
| None -> Map.add idx 1 map
let removeFromMap map idx =
let value = Map.tryfind idx map
match value with
| Some(x) ->
if x > 1 then
Map.add idx (x-1) map
else
Map.remove idx map
| None -> map
open MapHelper

Now I can adjust my sorted list implementation:

// a immutable sorted list - based on F# set
type 'a SortedFList =
{items: Tagged.Set<'a,Collections.Generic.IComparer<'a>>;
numbers: Map<'a,int>;
count: int}
member x.Min = x.items.MinimumElement
member x.Items =
**seq {
for item in x.items ****do
for number in [1..x.GetCount item] ****do
yield item}**
member x.Length = x.count
member x.IsEmpty = x.items.IsEmpty
member x.GetCount item =
match Map.tryfind item x.numbers with
| None -> 0
| Some(y) -> y
static member FromList(list, sortFunction) =
let comparer = FComparer<'a>.Create(sortFunction)
let m = list |> List.fold_left addToMap Map.empty
{new 'a SortedFList with
items = Tagged.Set<'a>.Create(comparer,list) and
numbers = m and
count = list.Length}
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);
numbers = addToMap x.numbers y;
count = x.count + 1}
member x.Remove(y) =
if x.GetCount y > 0 then
{x with
items = x.items.Remove(y);
numbers = removeFromMap x.numbers y;
count = x.count - 1}
else
x

Tags:

F#,

immutable map vs. dictionary,

immutable set,

immutable sorted list,

red-black trees
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 set,

immutable sorted list,

red-black trees