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

In the last post I show how we can calculate clusters of n-dimensional Objects with the K-means-Algorithm in F#. This time I will simplify the code by using the built-in type vector.

First of all we redefine the interface for “clusterable” objects:

type IClusterable =
  abstract DimValues: vector with get

This time we do not need any dimension information – the vector type will care about this. Now we can reduce our distance function to:

let calcDist (p1:vector) (p2:vector) = (p1 - p2).Norm

The function Norm calculates the 2-Norm of a vector.

So calcDist will still compute the n-dimensional Euclidean distance.

The next step is the definition of a n-dimensional Centroid type. This time we will only use a type alias of vector:

type Centroid = vector

The calculation of the centroid and the centroid error can be written as:

let calcCentroid (items:'a list when 'a :> IClusterable)
     (oldCentroid:Centroid) =
  let count = items.Length
  if count = 0 then oldCentroid else  
  let sum =
    items
      |> List.fold_left 
        (fun vec item -> vec + item.DimValues) // vector addition
        (nullVector oldCentroid)
   
  sum * (1./(count |> float))  // multiply with scalar
     

let calcError centroid (items:'a list when 'a :> IClusterable) =
  let sq x = x * x

  items
    |> List.sum_by (fun i -> calcDist centroid i.DimValues |> sq)

The calcError function is straight forward but not perfect in terms of performance. As we use the calcDist function and hence the 2-Norm the function will first calculate a square root and then squares the result.

The rest of the code is pretty much same as in the last post:

/// creates n-dimensional 0 - vector
let nullVector (v:vector) = v * 0.
    
type Cluster<'a> when 'a :> IClusterable =
  {Items: 'a list;
   Count: int;
   Centroid: Centroid;
   Error: float}

  member x.Print =
     printfn "(Items: %d, Centroid: %A, Error: %.2f)"
       x.Count x.Centroid x.Error

  static member CreateCluster (item:'a) =
    let items = [item]
    let empty = nullVector item.DimValues

    let centroid = calcCentroid items empty
    {new Cluster<'a> with
      Items = items and
      Count = 1 and
      Centroid = centroid and
      Error = calcError centroid items}

  member x.EvolveCluster (items:'a list) =
    let l = items.Length
    let centroid = calcCentroid items x.Centroid
    {x with
      Items = items;
      Count = l;
      Centroid = centroid;
      Error = calcError centroid items} 

let rand = new Random()  

let InitClusters (k:int)
      (items:'a array when 'a :> IClusterable)  =
  let length = items.Length
  let getInitItem() = items.[rand.Next length]
  Array.init k (fun x ->
                  getInitItem()
                    |> Cluster<'a>.CreateCluster)
                    
                    
let AssignItemsToClusters k (clusters:Cluster<'a> array)
      (items:'a seq when 'a :> IClusterable) =
  if k <= 0 then failwith "KMeans needs k > 0"
  let findNearestCluster (item:'a) =
    let minDist,nearest,lastPos =
      clusters
        |> Array.fold_left
            (fun (minDist,nearest,pos) cluster ->
               let distance = calcDist item.DimValues (cluster.Centroid)
               if distance < minDist then
                 (distance,pos,pos+1)
               else
                 (minDist,nearest,pos+1))
            (Double.PositiveInfinity,0,0)
    nearest

  let assigned =
    items
      |> Seq.map (fun item -> item,findNearestCluster item)

  let newClusters = Array.create k []
  for item,nearest in assigned do
    newClusters.[nearest] <- item::(newClusters.[nearest])

  clusters
    |> Array.mapi (fun i c -> c.EvolveCluster newClusters.[i])  

    
let calcClusterError (clusters:Cluster<'a> array) =
  clusters
    |> Array.fold_left (fun acc cluster -> acc + cluster.Error) 0.  
                      
let kMeansClustering K epsilon
       (items:'a array when 'a :> IClusterable) =
  let k = if K <= 0 then 1 else K
  let rec clustering lastError (clusters:Cluster<'a> array) =
    let newClusters =
      AssignItemsToClusters k clusters items
    let newError = calcClusterError newClusters

    if abs(lastError - newError) > epsilon then
      clustering newError newClusters
    else
      newClusters,newError    

  InitClusters k items
    |> clustering Double.PositiveInfinity

This vector approach shortens the code for the kMeans algorithm, but has a little longer runtime. I am interested in any suggestions.

The K-means-Algorithm is one of the simplest unsupervised learning algorithms that solve the well known clustering problem. In this article I will show how we can implement this in F#.

First of all we define an interface for “clusterable” objects:

The next step is to define a distance function. We will use n-dimensional Euclidean distance here.

Now we define a n-dimensional Centroid type. Our kMeans-Algorithm will minimize the squared distances to k centroids (or “means”).

The centroid of a finite set of n-dimensional points x₁, x₂, …, x_n is calculated as

We made a small modification – if we don’t have any items assigned to a cluster the centroid won’t change. This is important for the robustness of the algorithm.

Now we can calculate the squared errors to a centroid:

For storing cluster information we create a cluster type:

Now we need a function to initialize the clusters and a function to assign a items to the nearest cluster:

The last step is a function which calculates the squared error over all clusters:

Now it is an easy task to write the kMeans algorithm:

We can test this algorithm with random 2-dimensional points:

Next time I will show how we can simplify the code by using F#’s built-in type vector instead of array.

Last time I showed how one can solve the Euler Project – problem 53 with the help of Dynamic Programming and a two-dimensional array. This time I will use another technique called (automatic) memoization.

First of all I need a memoization-function. There are two different approaches, one with a System.Collections.Generic.Dictionary and one with an immutable Map. You can read Don Syme’s blog posting to get more information about the differences.

let memoizeWithMap f =
  let cache = ref Map.empty
  fun x ->
    match (!cache).TryFind(x) with
      | Some res -> res
      | None ->
           let res = f x
           cache := (!cache).Add(x,res)
           res

open System.Collections.Generic

let memoizeWithDictionary f =
  let cache = Dictionary<_, _>()
  fun x ->
    let (found,result) = cache.TryGetValue(x)
    if found then
      result
    else
      let res = f x
      cache.[x] <- res
      res

With the help of one of this generic memoization-functions I can create a recursive function for the binomial coefficients, which memoizes intermediate data:

let rec binomial =
  let f (n,k) =
    if k = 0I || n = k then
      1I
    else
      binomial(n - 1I,k) + binomial(n - 1I,k - 1I)
  f |> memoizeWithDictionary

let answer =
      seq { for n in 2I .. 100I do
              for k in 2I .. n -> n,k }
       |> Seq.filter (fun (a,b) -> binomial (a,b) > 1000000I )
       |> Seq.length

answer |> printf "Answer: %A"

It turns out that memoizeWithDictionary is much faster for this problem. But with 160ms it is still slower than the comparable version with a two-dimensional array (45ms).

Claudio Cherubino (from fsharp.it/) posted his solution to Euler Project – problem 53. As I dealed a lot with Dynamic Programming in the recent time, I tried to solve the problem with a dynamic program in F#.

Project Euler – Problem 53:

How many values of C(n,k), for 1 ≤ n ≤ 100, exceed one-million?

Remark: C(n,k) are the binomial coefficients.

As it turned out, this is not that complicated if one knows the recursive function for the binomial coefficients (see Wikipedia):

with

This is easily transformed into a F# program:

let binomials = Array2.create 101 101 1I
let answer = ref 0
for n in [1..100] do
  for k in [1..n - 1] do
    binomials.[n, k] <- binomials.[n - 1,k] + binomials.[n - 1,k - 1]
    if binomials.[n, k] > 1000000I then
      answer := !answer + 1

!answer |> printf "Answer: %A"

Claudio’s program took 1315ms on my computer. The dynamic program needs only 63ms. But we can still do better if we use the symmetry of Pascal’s triangle.

This leads to an algorithm, which calculates only half of the binomial coefficients.

let binomials = Array2.create 101 101 1I
let answer = ref 0
for n in [1..100] do
  for k in [1..n/2] do
    let b = binomials.[n - 1,k] + binomials.[n - 1,k - 1]
    binomials.[n, k] <- b
    binomials.[n, n - k] <- b
    if b > 1000000I then
      if k = n-k then
        answer := !answer + 1
      else
        answer := !answer + 2

!answer |> printf "Answer: %A"

This version needs only 45ms – but we are not ready. I mentioned Pascal’s triangle and its symmetry. But we can use another property. We don’t have to calculate the complete row, if we exceed 100000. All values behind this threshold have to be greater.

let binomials = Array2.create 101 101 1I
let answer = ref 0
for n in [1..100] do
  let threshold_reached = ref false
  let c = ref 0
  for k in [1..n/2] do
    if not !threshold_reached then
      let b = binomials.[n - 1,k] + binomials.[n - 1,k - 1]
      binomials.[n, k] <- b
      binomials.[n, n - k] <- b
      if b > 1000000I then
        threshold_reached := true
      else
        c := !c + 1

  if !threshold_reached then
    answer := !answer + (n - 1) - (2 * !c)

!answer |> printf "Answer: %A"

This final version took only 29 ms.

In the next posting I will show a version using memoization.

The “Subset Sum”-problem is given as the following:

SUBSET SUM
Input: Numbers a₁, a₂, . . . , a_n, S ∈ N.
Question: Is there a subset I ⊆ {1,…,n} with ∑ a_i = S?

Finding a solution for this decision problem is a very easy task in F#.

let hasSubsetSum_Naive (numbers: int list) S =
  let rec hasSubsetSum (a: int list) lastSum =
    match a with 
      | [] -> false
      | x::rest -> 
        if lastSum + x = S then
          true
        elif lastSum + x > S then
          false
        else
          hasSubsetSum rest lastSum || hasSubsetSum rest (lastSum+x)
  
  hasSubsetSum numbers 0

let numbers = [ 5;4;3;6;7;12 ]
let searchedSum = 33  
hasSubsetSum_Naive numbers searchedSum

Of course this small program can be easily adjusted to give the subset I back. Unfortunately this naïve approach leads to a running time of O(2^n).

But if S is small we can build a dynamic program and decide the problem in O(n*S) time.

This can be easily transformed into F# code.

let hasSubsetSum (numbers: int array) S =
   if numbers |> Array.exists (fun x -> x = S) then
     true
   else
     let a = numbers |> Array.filter (fun x -> x < S)      
     let n = a.Length
     if n = 0 then
       false
     else
       let v = Array2.create n (S+1) 0
       let u = Array2.create n (S+1) false
       let t = Array2.create n (S+1) 0
       
       for j in [1..S] do
         for i in [0..n-1] do                           
           if j - a.[i] >= 0 && not u.[i,j - a.[i]] then
             v.[i,j] <- t.[i,j - a.[i]] + a.[i]
           if ((i = 0) || (i > 0 && t.[i-1,j] <> j)) && v.[i,j] = j then
             u.[i,j] <- true
           if v.[i,j] = j then
             t.[i,j] <- j
           else
             if i > 0 then
               t.[i,j] <- max t.[i-1,j] t.[i,j-1]
             else
               t.[i,j] <- t.[0,j-1]
               
       t.[n-1,S] = S

If we want to calculate the distance between two objects, we need some sort of distance function. I recently showed how we can compute the “edit distance” between two strings (see Damerau-Levenshtein-Distance in F# – part I, part II and part III). This time I will consider the distance between two points in the plane and on the surface of the earth.

First of all we need some sort of location type, which stores information about the coordinates (I used this type before). I will use the “Units of Measure”-feature in F# to distinct between <degree> vs. <radian> and <m> vs. <km>. If you are not familiar with this concept see Andrew Kennedy’s excellent blog series about Units of Measures in F#.

open Microsoft.FSharp.Math.SI
  
[<Measure>]
type degree

[<Measure>]
type radian =
  static member per_degree = Math.PI/180.0<degree/radian>
  
[<Measure>]
type km =  
  static member per_meter = 1000.<m/km>

type Location =
  {Latitude:float<degree>; 
   Longitude:float<degree> }
    
  member x.YPos = x.Longitude
  member x.XPos = x.Latitude        
  member x.Longitude_radian = x.Longitude * radian.per_degree  
  member x.Latitude_radian = x.Latitude * radian.per_degree   
  member x.Coordinates = (x.Longitude,x.Latitude)  
  
  static member CreateLocation(latitude, longitude) = 
    {new Location with
      Latitude = latitude and
      Longitude = longitude}

Now we can easily compute the Euclidean distance for two points in the plane.

let sq x = x * x
let CalcEuclideanDistance (s:Location) (t:Location) =
  let d1 = (t.Longitude - s.Longitude) / 1.<degree> 
  let d2 = (t.Latitude - s.Latitude) / 1.<degree>
  ((sq d1 + sq d2) |> Math.Sqrt) * 1.<m>

If we want to approximate the distance of two cities on the surface of earth, we can use the “Great circle distance“.

“The great-circle distance is the shortest distance between any two points on the surface of a sphere measured along a path on the surface of the sphere (as opposed to going through the sphere’s interior)” – Wikipedia

let kmFactor = 6372.795<km>
let sin_rad x = Math.Sin(x / 1.<radian>)
let cos_rad x = Math.Cos(x / 1.<radian>)

/// Great Circle Distance 
let CalcGreatCircleDistance (s:Location) (t:Location)=
  if s = t then
    0.<m>
  else
    let factor = kmFactor * km.per_meter
    let b =
         sin_rad s.Latitude_radian * sin_rad t.Latitude_radian +
         cos_rad s.Latitude_radian * cos_rad t.Latitude_radian *
           cos_rad (t.Longitude_radian - s.Longitude_radian) 
    Math.Acos(b) * factor

In one of my next postings I will show a algorithm, that calculates line segment intersections. As a prerequisite we need an algorithm, which calculates the intersection of two lines. In this post I will consider the following intersection of two lines in the euclidean plan:

We can write this as an equation system with two variables and two equations:

• Ax + r (Bx – Ax) = Cx + s (Dx – Cx)
• Ay + r (By – Ay) = Cy + s (Dy – Cy)

After solving this system we can calculate the intersection:

• Px = Ax + r (Bx – Ax)
• Py = Ay + r (By – Ay)

Putting this all together we can derive the following F#-code:

let calcIntersection (A:Location, B:Location, C:Location, D:Location) =
  let (Ax,Ay,Bx,By,Cx,Cy,Dx,Dy) =
     (A.XPos, A.YPos, B.XPos, B.YPos, C.XPos, C.YPos, D.XPos, D.YPos)
  let d = (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx)  

  if  d = 0 then
    // parallel lines ==> no intersection in euclidean plane
    None
  else
    let q = (Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy) 
    let r = q / d
    let p = (Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay)
    let s = p / d

    if r < 0. or r > 1. or s < 0. or s > 1. then
      None // intersection is not within the line segments
    else
      Some(
        (Ax+r*(Bx-Ax)),  // Px
        (Ay+r*(By-Ay)))  // Py

Remarks:

1. If one given line degenerates into a point, then the algorithm gives no intersection.
2. If the given lines are parallel, then the algorithm gives no intersection, even if the lines have an overlap.

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        

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.

In the first part of this series I showed a naïve algorithm for the Damerau-Levenshtein distance which needs O(m*n) space. In the last post I improved the algorithm to use only O(m+n) space. This time I will show a more functional implementation which uses only immutable F#-Lists and works still in O(m+n) space. This version doesn’t need any mutable data.

/// Calcs the damerau levenshtein distance.    
let calcDL (a:'a array) (b: 'a array) =       
  let n = a.Length + 1
  let m = b.Length + 1
  
  let processCell i j act l1 l2 ll1 =
    let cost = 
      if a.[i-1] = b.[j-1] then 0 else 1
    let deletion = l2 + 1
    let insertion = act + 1
    let substitution = l1 + cost
    let min1 =  
      deletion 
      |> min insertion 
      |> min substitution

    if i > 1 && j > 1 &&
      a.[i-1] = b.[j-2] && a.[i-2] = b.[j-1] then
        min min1 <| ll1 + cost
    else
      min1
  
  let processLine i lastL lastLastL =
    let processNext (actL,lastL,lastLastL) j =
      match actL with 
        | act::actRest -> 
          match lastL with
            | l1::l2::lastRest -> 
              if i > 1 && j > 1 then
                match lastLastL with
                  | ll1::lastLastRest -> 
                    (processCell i j act l1 l2 ll1 :: actL,
                     l2::lastRest,
                     lastLastRest)
                  | _ -> failwith "can't be"
              else
                (processCell i j act l1 l2 0 :: actL,
                 l2::lastRest,
                 lastLastL)                 
            | _ -> failwith "can't be"
        | [] -> failwith "can't be"
      
    let (act,last,lastLast) =
      [1..b.Length]
        |> List.fold_left processNext ([i],lastL,lastLastL)
    act |> List.rev
    
  let (lastLine,lastLastLine) =               
    [1..a.Length]
      |> List.fold_left
          (fun (lastL,lastLastL) i -> 
             (processLine i lastL lastLastL,lastL))
          ([0..m-1],[])
              
  lastLine.[b.Length]    
 
let damerauLevenshtein(a:'a array) (b:'a array) =
  if a.Length > b.Length then
    calcDL a b
  else
    calcDL b a

I admit the code is still a little messy but it works fine. Maybe I will find the time to cleanup a bit and post a final version.