Rash thoughts about .NET, C#, F# and Dynamics NAV.

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