06
Sep 11

Record Linkage Algorithms in F# – Jaro-Winkler Distance (Part 2)

Last time we dove into the Jaro distance algorithm and picked apart how each of its components are calculated. However, from a modern perspective Jaro alone is a rather weak method of string matching. It was Winkler’s extension that brought this algorithm into widespread modern use.

Matthew Jaro’s insight when inventing the Jaro distance algorithm was that humans tend to make certain kinds of errors. However, while working on the 1990 census William Winkler had an additional insight: these kinds of errors are much more likely to occur later in the string. By simply wrapping Jaro’s algorithm to forgive some penalty according to the similarity of the first few characters, Winkler was able to get significantly better results with little additional overhead.

Winker's Extension

Here we see that the Jaro-Winkler distance (dw) is equal to the result of the Jaro distance (dj) plus one minus that same value times some weighted metric (lp). This is a great mathematical trick for two reasons. First, as long as the weighted metric (lp) doesn’t exceed 1, the final result will stay within the 0-1 range of the Jaro metric. Second, it guarantees that the result of Jaro-Winkler will never be lower than the result of Jaro alone. It effectively lets Winkler enrich the results of Jaro by filling in the remaining gap.

The meaning of the weighted metric (lp) is even more simple. Here l is just the number of initial characters which match, up to a maximum of four. Meanwhile p is a weight which can be up to 1/4, or one over the maximum possible value of l.

As p gets larger and larger, more and more of the gap will be filled in by Winkler’s extension. When p is 1/4, strings where first four characters match will always be given a perfect score. Just as we’d never want strings like “JOHN” and “JOHNSON” to be considered a perfect match, we’d never want to use a p value of 1/4. After much experimentation, Winkler recommends using a p value of 0.1, which is also what I use.

Now that we’ve covered how the math works, let’s take a look at an actual implementation. If you’d like to see an implementation of the Jaro distance algorithm take a look at the previous installment of Record Linkage Algorithms in F#.

 1: /// Calculate the Jaro-Winkler distance of s1 and s2
 2: let jaroWinkler s1 s2 = 
 3:     let jaroScore = jaro s1 s2
 4:     // Accumulate the number of matching initial characters
 5:     let maxLength = (min s1.Length s2.Length) - 1
 6:     let rec calcL i acc =
 7:         if i > maxLength || s1.[i] <> s2.[i] then acc
 8:         else calcL (i + 1) (acc + 1.0)
 9:     let l = min (calcL 0 0.0) 4.0
10:     // Calculate the JW distance
11:     let p = 0.1
12:     jaroScore + (l * p * (1.0 - jaroScore))

In my implementation I’ve allowed for some slight inefficiency in order to make it easier to play with the p value and number of characters examined. So far I’ve found Winkler’s choice of four characters to be the best, which incidentally has been shown as a great number of initial characters to look at when using a number of record linkage algorithms on things in the English language. However, I suspect that other values may work better when working in other languages.

The math here is so simple that I don’t feel it’s worth breaking down further, but I’ve included my tests built from the examples in the Jaro-Winkler distance Wikipedia article. For a fuller understanding just break out the debugger and play a bit on your own.

14: open Xunit
15: 
16: [<Fact>]
17: let ``Jaro-Winkler identity test`` () = 
18:     let result = jaroWinkler "RICK" "RICK"
19:     Assert.Equal("1.000", String.Format("{0:0.000}", result))
20: 
21: [<Fact>]
22: let ``Jaro-Winkler martha test`` () = 
23:     let result = jaroWinkler "MARTHA" "MARHTA"
24:     Assert.Equal("0.961", String.Format("{0:0.000}", result))
25: 
26: [<Fact>]
27: let ``Jaro-Winkler dwayne test`` () = 
28:     let result = jaroWinkler "DWAYNE" "DUANE"
29:     Assert.Equal("0.840", String.Format("{0:0.000}", result))
30: 
31: [<Fact>]
32: let ``Jaro-Winkler dixon test`` () =
33:     let result = jaroWinkler "DIXON" "DICKSONX"
34:     Assert.Equal("0.813", String.Format("{0:0.000}", result))
35: 

val jaroWinkler : 'a -> 'b -> float

Full name: Snippet.jaroWinkler

Calculate the Jaro-Winkler distance of s1 and s2

val s1 : 'a
val s2 : 'b
val jaroScore : float

  type: float
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<float>
  implements: System.IEquatable<float>
  inherits: System.ValueType

val maxLength : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

val min : 'T -> 'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.min

val calcL : (int -> float -> float)
val i : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

val acc : float

  type: float
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<float>
  implements: System.IEquatable<float>
  inherits: System.ValueType

val l : float

  type: float
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<float>
  implements: System.IEquatable<float>
  inherits: System.ValueType

val p : float

  type: float
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<float>
  implements: System.IEquatable<float>
  inherits: System.ValueType

val result : float

  type: float
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<float>
  implements: System.IEquatable<float>
  inherits: System.ValueType

module String

from Microsoft.FSharp.Core

Multiple items

type Format<'Printer,'State,'Residue,'Result,'Tuple> = PrintfFormat<'Printer,'State,'Residue,'Result,'Tuple>

Full name: Microsoft.FSharp.Core.Format<_,_,_,_,_>

  type: Format<'Printer,'State,'Residue,'Result,'Tuple>
  inherits: PrintfFormat<'Printer,'State,'Residue,'Result>

——————–

type Format<'Printer,'State,'Residue,'Result> = PrintfFormat<'Printer,'State,'Residue,'Result>

Full name: Microsoft.FSharp.Core.Format<_,_,_,_>

In the next installment of Record Linkage Algorithms in F# we’ll take a look a method for efficient token based matching with Jaro-Winkler. Stay tuned!

Edit: All current code for this series is now available on github.


02
Sep 11

Record Linkage Algorithms in F# – Jaro-Winkler Distance (Part 1)

When first approaching the task of record linkage I was initially overwhelmed by the huge number of different algorithms available for comparing strings. Now I know that the secret to finding your way in this sea of algorithms is two fold. First, know that many are outdated and have newer and better implementations, so they can be ignored. Second, of the newest extension of each algorithm, each has a particular use depending on the kind of data you’re comparing.

Jaro-Winkler distance is a particularly good choice when comparing short strings of human entered data, such as names. This is due to it’s relative robustness against letter transpositions and it’s weighting of similarity toward the beginning of the string. When it comes to comparing names, a slightly customized version of tokenized Jaro-Winkler is one of the first things in my toolbox that I reach for.

Jaro-Winkler distance also has the benefit of being a rather easy to understand algorithm. It’s composed of two parts, Jaro’s original algorithm and Winkler’s extension.  In this installment we’ll roll up our sleeves and dig into the first part of this algorithm, Jaro distance.

The Jaro Algorithm

This is the equation for Jaro distance. It’s made up of the average of three sub-calculations.

  1. The ratio of matching characters to the length of the first string.
  2. The ratio of matching characters to the length of the second string.
  3. The ratio of non-transpositions to the number matching of characters.

My implementation has been optimized a bit, but I think it’s still rather easy to understand.

 1: open System
 2: 
 3: /// Given an offset and a radius from that offset, 
 4: /// does mChar exist in that part of str?
 5: let inline existsInWin (mChar: char) (str: string) offset rad =
 6:     let startAt = max 0 (offset - rad)
 7:     let endAt = min (offset + rad) (String.length str - 1)  
 8:     if endAt - startAt < 0 then false
 9:     else
10:         let rec exists index =
11:             if str.[index] = mChar then true
12:             elif index = endAt then false
13:             else exists (index + 1)
14:         exists startAt
15: 
16: /// The jaro distance between s1 and s2
17: let jaro s1 s2 =
18:     
19:     // The radius is half of the lesser 
20:     // of the two string lengths rounded up.
21:     let matchRadius = 
22:         let minLen = 
23:             min (String.length s1) (String.length s2) in
24:               minLen / 2 + minLen % 2
25: 
26:     // An inner function which recursively finds the number  
27:     // of matched characters within the radius.
28:     let commonChars (chars1: string) (chars2: string) =
29:         let rec inner i result = 
30:             match i with
31:             | -1 -> result
32:             | _ -> if existsInWin chars1.[i] chars2 i matchRadius
33:                    then inner (i - 1) (chars1.[i] :: result)
34:                    else inner (i - 1) result
35:         inner (chars1.Length - 1) []
36: 
37:     // The sets of common characters and their lengths as floats 
38:     let c1 = commonChars s1 s2
39:     let c2 = commonChars s2 s1
40:     let c1length = float (List.length c1)
41:     let c2length = float (List.length c2)
42:     
43:     // The number of transpositions within 
44:     // the sets of common characters.
45:     let transpositions = 
46:         let rec inner cl1 cl2 result = 
47:             match cl1, cl2 with
48:             | [], _ | _, [] -> result
49:             | c1h :: c1t, c2h :: c2t -> 
50:                 if c1h <> c2h
51:                 then inner c1t c2t (result + 1.0)
52:                 else inner c1t c2t result
53:         let mismatches = inner c1 c2 0.0
54:         // If one common string is longer than the other
55:         // each additional char counts as half a transposition
56:         (mismatches + abs (c1length - c2length)) / 2.0
57: 
58:     let s1length = float (String.length s1)
59:     let s2length = float (String.length s2)
60:     let tLength = max c1length c2length
61: 
62:     // The jaro distance as given by 
63:     // 1/3 ( m2/|s1| + m1/|s2| + (mc-t)/mc )
64:     let result = (c1length / s1length +
65:                   c2length / s2length + 
66:                   (tLength - transpositions) / tLength)
67:                  / 3.0
68: 
69:     // This is for cases where |s1|, |s2| or m are zero 
70:     if Double.IsNaN result then 0.0 else result

We’re quite lucky to have examples of the algorithm in action available right in the Wikipedia article to use as unit tests. When optimizing, you couldn’t ask for more.

Take ‘DWAYNE’ and ‘DUANE’ for example. According to the article we should end up with the following results:

DWAYNE vs DUANE

So, let’s break it down. The lesser of the two strings, DUANE, is 5 characters long. When we set minLen to 5 in (minLen / 2 + minLen % 2 is 3), we get a radius of 3.

Next we find the common characters in each direction. Comparing at DWAYNE to DUANE with a radius of 3 we can see that D, A, N and E will match, giving us a c1 = “DANE”. Similarly, comparing at DUANE to DWAYNE we get exactly the same thing. That is, c2 = “DANE” as well.

As you might have guessed by the fact both sets of common strings are the same, we have zero transpositions in this instance.

So now, we just plug in the numbers and get 1/3 * (4/6 + 4/5 + (4-0)/4) = 0.822. Not too difficult, eh?

For a better understanding of how transpositions end up working out, try walking through the debugger with the MARTHA vs MARHTA test below.

72: open Xunit
73: 
74: [<Fact>]
75: let ``Jaro identity test`` () = 
76:     let result = jaro "RICK" "RICK"
77:     Assert.Equal("1.000", String.Format("{0:0.000}", result))
78: 
79: [<Fact>]
80: let ``Jaro martha test`` () =
81:     let result = jaro "MARTHA" "MARHTA"
82:     Assert.Equal("0.944", String.Format("{0:0.000}", result))
83: 
84: [<Fact>]
85: let ``Jaro dwayne test`` () = 
86:     let result = jaro "DWAYNE" "DUANE"
87:     Assert.Equal("0.822", String.Format("{0:0.000}", result))
88: 
89: [<Fact>]
90: let ``Jaro dixon test`` () =
91:     let result = jaro "DIXON" "DICKSONX"
92:     Assert.Equal("0.767", String.Format("{0:0.000}", result))
93: 
94: 

namespace System
val existsInWin : char -> string -> 'a -> 'b -> bool (requires member ( – ) and member ( + ))

Full name: Snippet.existsInWin

Given an offset and a radius from that office,
 does mChar exist in that part of str?

val mChar : char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

Multiple items

val char : 'T -> char (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.char

——————–

type char = Char

Full name: Microsoft.FSharp.Core.char

  type: char
  implements: IComparable
  implements: IConvertible
  implements: IComparable<char>
  implements: IEquatable<char>
  inherits: ValueType

val str : string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

Multiple items

val string : 'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

——————–

type string = String

Full name: Microsoft.FSharp.Core.string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val offset : 'a (requires member ( – ) and member ( + ))
val rad : 'b (requires member ( – ) and member ( + ))
val startAt : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val max : 'T -> 'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.max

val endAt : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val min : 'T -> 'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.min

type String =
  class
    new : char -> string
    new : char * int * int -> string
    new : System.SByte -> string
    new : System.SByte * int * int -> string
    new : System.SByte * int * int * System.Text.Encoding -> string
    new : char [] * int * int -> string
    new : char [] -> string
    new : char * int -> string
    member Chars : int -> char
    member Clone : unit -> obj
    member CompareTo : obj -> int
    member CompareTo : string -> int
    member Contains : string -> bool
    member CopyTo : int * char [] * int * int -> unit
    member EndsWith : string -> bool
    member EndsWith : string * System.StringComparison -> bool
    member EndsWith : string * bool * System.Globalization.CultureInfo -> bool
    member Equals : obj -> bool
    member Equals : string -> bool
    member Equals : string * System.StringComparison -> bool
    member GetEnumerator : unit -> System.CharEnumerator
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> System.TypeCode
    member IndexOf : char -> int
    member IndexOf : string -> int
    member IndexOf : char * int -> int
    member IndexOf : string * int -> int
    member IndexOf : string * System.StringComparison -> int
    member IndexOf : char * int * int -> int
    member IndexOf : string * int * int -> int
    member IndexOf : string * int * System.StringComparison -> int
    member IndexOf : string * int * int * System.StringComparison -> int
    member IndexOfAny : char [] -> int
    member IndexOfAny : char [] * int -> int
    member IndexOfAny : char [] * int * int -> int
    member Insert : int * string -> string
    member IsNormalized : unit -> bool
    member IsNormalized : System.Text.NormalizationForm -> bool
    member LastIndexOf : char -> int
    member LastIndexOf : string -> int
    member LastIndexOf : char * int -> int
    member LastIndexOf : string * int -> int
    member LastIndexOf : string * System.StringComparison -> int
    member LastIndexOf : char * int * int -> int
    member LastIndexOf : string * int * int -> int
    member LastIndexOf : string * int * System.StringComparison -> int
    member LastIndexOf : string * int * int * System.StringComparison -> int
    member LastIndexOfAny : char [] -> int
    member LastIndexOfAny : char [] * int -> int
    member LastIndexOfAny : char [] * int * int -> int
    member Length : int
    member Normalize : unit -> string
    member Normalize : System.Text.NormalizationForm -> string
    member PadLeft : int -> string
    member PadLeft : int * char -> string
    member PadRight : int -> string
    member PadRight : int * char -> string
    member Remove : int -> string
    member Remove : int * int -> string
    member Replace : char * char -> string
    member Replace : string * string -> string
    member Split : char [] -> string []
    member Split : char [] * int -> string []
    member Split : char [] * System.StringSplitOptions -> string []
    member Split : string [] * System.StringSplitOptions -> string []
    member Split : char [] * int * System.StringSplitOptions -> string []
    member Split : string [] * int * System.StringSplitOptions -> string []
    member StartsWith : string -> bool
    member StartsWith : string * System.StringComparison -> bool
    member StartsWith : string * bool * System.Globalization.CultureInfo -> bool
    member Substring : int -> string
    member Substring : int * int -> string
    member ToCharArray : unit -> char []
    member ToCharArray : int * int -> char []
    member ToLower : unit -> string
    member ToLower : System.Globalization.CultureInfo -> string
    member ToLowerInvariant : unit -> string
    member ToString : unit -> string
    member ToString : System.IFormatProvider -> string
    member ToUpper : unit -> string
    member ToUpper : System.Globalization.CultureInfo -> string
    member ToUpperInvariant : unit -> string
    member Trim : unit -> string
    member Trim : char [] -> string
    member TrimEnd : char [] -> string
    member TrimStart : char [] -> string
    static val Empty : string
    static member Compare : string * string -> int
    static member Compare : string * string * bool -> int
    static member Compare : string * string * System.StringComparison -> int
    static member Compare : string * string * System.Globalization.CultureInfo * System.Globalization.CompareOptions -> int
    static member Compare : string * string * bool * System.Globalization.CultureInfo -> int
    static member Compare : string * int * string * int * int -> int
    static member Compare : string * int * string * int * int * bool -> int
    static member Compare : string * int * string * int * int * System.StringComparison -> int
    static member Compare : string * int * string * int * int * bool * System.Globalization.CultureInfo -> int
    static member Compare : string * int * string * int * int * System.Globalization.CultureInfo * System.Globalization.CompareOptions -> int
    static member CompareOrdinal : string * string -> int
    static member CompareOrdinal : string * int * string * int * int -> int
    static member Concat : obj -> string
    static member Concat : obj [] -> string
    static member Concat<'T> : System.Collections.Generic.IEnumerable<'T> -> string
    static member Concat : System.Collections.Generic.IEnumerable<string> -> string
    static member Concat : string [] -> string
    static member Concat : obj * obj -> string
    static member Concat : string * string -> string
    static member Concat : obj * obj * obj -> string
    static member Concat : string * string * string -> string
    static member Concat : obj * obj * obj * obj -> string
    static member Concat : string * string * string * string -> string
    static member Copy : string -> string
    static member Equals : string * string -> bool
    static member Equals : string * string * System.StringComparison -> bool
    static member Format : string * obj -> string
    static member Format : string * obj [] -> string
    static member Format : string * obj * obj -> string
    static member Format : System.IFormatProvider * string * obj [] -> string
    static member Format : string * obj * obj * obj -> string
    static member Intern : string -> string
    static member IsInterned : string -> string
    static member IsNullOrEmpty : string -> bool
    static member IsNullOrWhiteSpace : string -> bool
    static member Join : string * string [] -> string
    static member Join : string * obj [] -> string
    static member Join<'T> : string * System.Collections.Generic.IEnumerable<'T> -> string
    static member Join : string * System.Collections.Generic.IEnumerable<string> -> string
    static member Join : string * string [] * int * int -> string
  end

Full name: System.String

  type: String
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val length : string -> int

Full name: Microsoft.FSharp.Core.String.length

val exists : (int -> bool)
val index : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val jaro : string -> string -> float

Full name: Snippet.jaro

The jaro distance between s1 and s2

val s1 : string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val s2 : string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val matchRadius : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val minLen : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val commonChars : (string -> string -> char list)
val chars1 : string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val chars2 : string

  type: string
  implements: IComparable
  implements: ICloneable
  implements: IConvertible
  implements: IComparable<string>
  implements: seq<char>
  implements: Collections.IEnumerable
  implements: IEquatable<string>

val inner : (int -> char list -> char list)
val i : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val result : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

property String.Length: int
val c1 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c2 : char list

  type: char list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<char>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<char>
  implements: Collections.IEnumerable

val c1length : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

Multiple items

val float : 'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

——————–

type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

  type: float<'Measure>
  implements: IComparable
  implements: IConvertible
  implements: IFormattable
  implements: IComparable<float<'Measure>>
  implements: IEquatable<float<'Measure>>
  inherits: ValueType

——————–

type float = Double

Full name: Microsoft.FSharp.Core.float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

Multiple items

module List

from Microsoft.FSharp.Collections

——————–

type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface Collections.IEnumerable
    interface Collections.Generic.IEnumerable<'T>
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    member Tail : 'T list
    static member Cons : head:'T * tail:'T list -> 'T list
    static member Empty : 'T list
  end

Full name: Microsoft.FSharp.Collections.List<_>

  type: List<'T>
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<'T>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<'T>
  implements: Collections.IEnumerable

val length : 'T list -> int

Full name: Microsoft.FSharp.Collections.List.length

val c2length : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val transpositions : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val inner : ('a list -> 'a list -> float -> float) (requires equality)
val cl1 : 'a list (requires equality)

  type: 'a list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<'a>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<'a>
  implements: Collections.IEnumerable

val cl2 : 'a list (requires equality)

  type: 'a list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<'a>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<'a>
  implements: Collections.IEnumerable

val result : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val c1h : 'a (requires equality)
val c1t : 'a list (requires equality)

  type: 'a list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<'a>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<'a>
  implements: Collections.IEnumerable

val c2h : 'a (requires equality)
val c2t : 'a list (requires equality)

  type: 'a list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<'a>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<'a>
  implements: Collections.IEnumerable

val mismatches : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val abs : 'T -> 'T (requires member Abs)

Full name: Microsoft.FSharp.Core.Operators.abs

val s1length : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val s2length : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val tLength : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

type Double =
  struct
    member CompareTo : obj -> int
    member CompareTo : float -> int
    member Equals : obj -> bool
    member Equals : float -> bool
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> System.TypeCode
    member ToString : unit -> string
    member ToString : string -> string
    member ToString : System.IFormatProvider -> string
    member ToString : string * System.IFormatProvider -> string
    static val MinValue : float
    static val MaxValue : float
    static val Epsilon : float
    static val NegativeInfinity : float
    static val PositiveInfinity : float
    static val NaN : float
    static member IsInfinity : float -> bool
    static member IsNaN : float -> bool
    static member IsNegativeInfinity : float -> bool
    static member IsPositiveInfinity : float -> bool
    static member Parse : string -> float
    static member Parse : string * System.Globalization.NumberStyles -> float
    static member Parse : string * System.IFormatProvider -> float
    static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> float
    static member TryParse : string * float -> bool
    static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * float -> bool
  end

Full name: System.Double

  type: Double
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

Double.IsNaN(d: float) : bool
Multiple overloads

String.Format(format: string, args: obj []) : string

String.Format(format: string, arg0: obj) : string

String.Format(provider: IFormatProvider, format: string, args: obj []) : string

String.Format(format: string, arg0: obj, arg1: obj) : string

String.Format(format: string, arg0: obj, arg1: obj, arg2: obj) : string

I hope you enjoyed this installment of Record Linkage Algorithms in F#. Next time we’ll explore the Winkler extension to this algorithm and take a look at why weighting errors earlier in the string more heavily ends up giving significantly better results.

Edit: All current code for this series is now available on github.


05
Apr 11

F# and the DLR at Dev Day for NSWC Dahlgren

Just yesterday I gave a presentation on F# and the DLR for the Naval Surface Warfare Center. Many thanks to Kevin Hazzard and Chris Bowen for recommending me. It was a fantastic opportunity to speak on the benefits of F# to an entirely new audience and I learned a few things about the DLR along the way.

Despite disliking dynamic languages in practice because of their lack of safety, I must admit that the DLR allows you to do quite a few very interesting things.

First, you can embed DLR language code right into html and so build Silverlight applications with no backing assembly. This is quite interesting as it makes the web development story for Silverlight much more attractive. Read more about this feature on the DLR section of the Silverlight Website.

Second, it’s quite easy to embed DLR languages into your application. With just about three lines of code I was able to build a IronPython query window right into a ListView. The possibilities for live debugging and building query DSLs here are huge.

Finally, the DLR is a great platform for building your own DSL. You need only to Parse and Lex your way to a DLR abstract syntax tree, sprinkle in a few rules, and you’ve got your own language. This is also where I see the marriage of F# and the DLR as F# is an ideal language to do this in. For an example of a really nice implementation of a DLR language in F#, take a look at IronJS.

Click here to download my slides, as well as the code used in this presentation.


27
Mar 11

Some Recent Talks (with slides and code)

I’ve given quite a few talks over the last couple of months and at each and every one I promised to post my content shortly afterwards here on my blog.

However, due to some extreme laziness early on coupled with a crazy schedule and some unfortunate (but thankfully temporary) health problems more recently, I’ve failed to live up to those promises. Sorry guys, here’s the slides and code I promised. Better late than never, right?

How you can get started with F# today

I gave this talk at the local .NET meeting the monday night of the MVP Summit.  It’s a short (15 minutes) one-two punch of why you might care about F# and where you can find out more.  Very well received.

Getting the MVVM Kicked Out of Your F#’n Monads

This presentation is from the most recent NYC Code Camp. The title started out as a joke with Steve Bohlen, mentioning on twitter that all the submitted talks had to do with MVVM. I wasn’t really going to do it, but when he said he’d automatically accept something with such a title, I decided to use it as a chance to explain computation expressions to a room full of people new to F#. It actually went really well considering, the post-talk reviews were fantastic.

Fun and Games in F#

My MVP2MVP talk from the MVP summit’s very first F# track. It’s a meta-talk about how to give a good F# talk, and how to build a stronger F# community.

08
Feb 11

The Road to Functional Programming in F# – From Imperative to Computation Expressions

In F# there are a lot of options when it comes to choosing the style in which you will perform a computation.  So, for our last meeting of the the NYC F# User Group I decided to try and build a general understanding of how the different styles are related to each other through trying them and discussing our results. Come along with us and explore five of different styles of programming in F#.

For our example I chose Project Euler #1 as it’s simple and wouldn’t get in the way of contrasting the different computation styles.

Find the sum of all the multiples of 3 or 5 below 1000.

As there are a lot of people out there that are new to F#, let’s start with an imperative approach.  That way we can all feel comfortable and see how the other styles relate.

let pe1_while limit =
    let mutable acc = 0
    let mutable x = 0
    while x < limit do
        if x % 5 = 0 || x % 3 = 0 then acc <- acc + x
        x <- x + 1
    acc

pe1_while 1000F# Web Snippets

val pe1_while : int -> int

Full name: Untitled.pe1_while

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val mutable acc : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val mutable x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Next, let’s move on to doing the same thing recursively.  This transition is the first step on the long road of functional programming and it’s important that new users see how the two basic patterns map to each other.  For this reason, I kept everything but the style of computation the same.

let pe1_rec limit =
    let rec inner_pe1 x acc =
        if x < limit then
            if x % 5 = 0 || x % 3 = 0 then
                inner_pe1 (x + 1) (x + acc)
            else
                inner_pe1 (x + 1) acc
        else acc
    inner_pe1 0 0F# Web Snippets

val pe1_rec : int -> int

Full name: Untitled.pe1_rec

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val inner_pe1 : (int -> int -> int)

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val acc : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

As you can see, the combination of the first if and the recursive calls correspond to the while statement.  The predicate remains the same.  The biggest conceptual hurdle for new users here is that for both predicates a course of action must be explicitly specified in both the success and failure case.

Another important idea here is that when doing recursion you don’t want to leave anything left undone on the stack. If you do, the compiler can’t do tail call optimization. Without tail call optimization each recursive call will create an additional stack frame. This slows things down and can even crash your program by overflowing the stack if the recursion goes too deep. As long as you don’t leave anything left undone your recursive function will run just as fast as a while loop.

I constructed this example with the thought that it would be best to avoid having to explain too many new constructs at once.  However, while discussing this solution one new user remarked that this looked like spaghetti code.  In response to this Paul, one of our more advanced users, whipped up a much nicer solution utilizing pattern matching.

let pe1_rec2 limit =
    let rec inner_pe1 acc = function
        | 1                     -> acc
        | i when (i % 3 = 0)
              || (i % 5 = 0)    -> inner_pe1 (acc + i) (i - 1)
        | i                     -> inner_pe1 acc       (i - 1)
    inner_pe1 0 (limit - 1) F# Web Snippets

val pe1_rec2 : int -> int

Full name: Untitled.pe1_rec2

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val inner_pe1 : (int -> int -> int)

val acc : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val i : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Now that’s some pretty code!  While it may have some intermediate concepts, the recursion looks just beautiful when structured with a pattern match.

Still, to most I think this hardly seems worth giving up mutation for.  This is why we should move on to pipelines and comprehensions next.

let pe1_seq limit =
    seq { 0 .. limit - 1 }
    |> Seq.filter (fun x -> x % 5 = 0 || x % 3 = 0)
    |> Seq.sumF# Web Snippets

val pe1_seq : int -> int

Full name: Untitled.pe1_seq

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Multiple items

val seq : seq<‘T> -> seq<‘T>

Full name: Microsoft.FSharp.Core.Operators.seq

——————–

type seq<‘T> = System.Collections.Generic.IEnumerable<‘T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<‘T>
inherits: System.Collections.IEnumerable

module Seq

from Microsoft.FSharp.Collections

val filter : (‘T -> bool) -> seq<‘T> -> seq<‘T>

Full name: Microsoft.FSharp.Collections.Seq.filter

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val sum : seq<‘T> -> ‘T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum

While bound to perform somewhat slower due to the use of sequences, it’s hard to imagine a more conceptually elegant solution to this problem. In comparison to the imperative version, the sequence comprehension takes on the role of both the while loop and the incrementor in generating the sequence values, the filter acts as the predicate and the sum as the accumulator.

The final two examples I’ll show you were more for fun and to provide a challenge to the intermediate and experienced users.  Conquering folding and unfolding were some of the biggest hurdles I faced when learning functional programming.  Just getting comfortable with how accumulators work takes some time for everyone.  For practice let’s use fold in our pipeline instead of filter and sum.

let pe1_fold limit =
    Seq.init limit id
    |> Seq.fold (fun acc x -> if x % 5 = 0 || x % 3 = 0
                              then acc + x 
                              else acc) 0F# Web Snippets

val pe1_fold : int -> int

Full name: Untitled.pe1_fold

val limit : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

module Seq

from Microsoft.FSharp.Collections

val init : int -> (int -> ‘T) -> seq<‘T>

Full name: Microsoft.FSharp.Collections.Seq.init

val id : ‘T -> ‘T

Full name: Microsoft.FSharp.Core.Operators.id

val fold : (‘State -> ‘T -> ‘State) -> ‘State -> seq<‘T> -> ‘State

Full name: Microsoft.FSharp.Collections.Seq.fold

val acc : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

val x : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

Here we took a somewhat different route when generating sequence values by using the Seq.init function.  As I discussed in my Ted Neward’s Folding Challenge post, the contents of the folding function can be directly mapped to the imperative and recursive solutions.  Just as in the first two examples the adding is done explicitly right along with the application of the predicate.   The biggest conceptual difference in this example is that the accumulator is passed as the return value of each call to fold instead of being kept in a mutable variable as in the imperative version or explicitly passed forward as in the recursive.

Finally, as a challenge to the most experienced users let’s see if we can do this with a computation expression.

type Euler1Builder() =
    member b.Combine(x, y) = x + y
    member b.Zero() = 0
    member b.Yield(x) = if x % 5 = 0 || x % 3 = 0 then x else 0
    member b.For(vals, f) =
        vals |> Seq.fold (fun s n -> b.Combine(s, f n)) (b.Zero()) 

let eb = new Euler1Builder()

let pe1_eb limit = eb { for x = 0 to limit - 1 do yield x }F# Web Snippets

type Euler1Builder =
class
new : unit -> Euler1Builder
member Combine : x:int * y:int -> int
member For : vals:seq<‘a> * f:(‘a -> int) -> int
member Yield : x:int -> int
member Zero : unit -> int
end

Full name: Untitled.Euler1Builder

val b : Euler1Builder

member Euler1Builder.Combine : x:int * y:int -> int

Full name: Untitled.Euler1Builder.Combine

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val y : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

member Euler1Builder.Zero : unit -> int

Full name: Untitled.Euler1Builder.Zero

member Euler1Builder.Yield : x:int -> int

Full name: Untitled.Euler1Builder.Yield

member Euler1Builder.For : vals:seq<‘a> * f:(‘a -> int) -> int

Full name: Untitled.Euler1Builder.For

val vals : seq<‘a>

type: seq<‘a>
inherits: System.Collections.IEnumerable

val f : (‘a -> int)

module Seq

from Microsoft.FSharp.Collections

val fold : (‘State -> ‘T -> ‘State) -> ‘State -> seq<‘T> -> ‘State

Full name: Microsoft.FSharp.Collections.Seq.fold

val s : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

val n : ‘a
member Euler1Builder.Combine : x:int * y:int -> int
member Euler1Builder.Zero : unit -> int

val eb : Euler1Builder

Full name: Untitled.eb

val pe1_eb : int -> int

Full name: Untitled.pe1_eb

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

This first attempt is what I showed off at our user group meeting.  It’s embarrassingly ugly and ends up just being a convoluted way to generate a sequence and fold over the values.  Since the meeting I’ve fiddled with it a bit and have come up with a solution I like much more.

type Euler1Builder2() =
    member b.Yield(x) = if x % 5 = 0 || x % 3 = 0 then x else 0
    member b.For(generated, f) = generated |> Seq.map (fun x -> f x)
    member b.Run(filtered: int seq) = filtered |> Seq.sum 

let eb2 = new Euler1Builder2()

let pe1_eb2 limit = eb2 { for x = 0 to limit - 1 do yield x }F# Web Snippets

type Euler1Builder2 =
class
new : unit -> Euler1Builder2
member For : generated:seq<‘a> * f:(‘a -> ‘b) -> seq<‘b>
member Run : filtered:seq<int> -> int
member Yield : x:int -> int
end

Full name: Untitled.Euler1Builder2

val b : Euler1Builder2

member Euler1Builder2.Yield : x:int -> int

Full name: Untitled.Euler1Builder2.Yield

val x : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

member Euler1Builder2.For : generated:seq<‘a> * f:(‘a -> ‘b) -> seq<‘b>

Full name: Untitled.Euler1Builder2.For

val generated : seq<‘a>

type: seq<‘a>
inherits: System.Collections.IEnumerable

val f : (‘a -> ‘b)

module Seq

from Microsoft.FSharp.Collections

val map : (‘T -> ‘U) -> seq<‘T> -> seq<‘U>

Full name: Microsoft.FSharp.Collections.Seq.map

val x : ‘a

member Euler1Builder2.Run : filtered:seq<int> -> int

Full name: Untitled.Euler1Builder2.Run

val filtered : seq<int>

type: seq<int>
inherits: System.Collections.IEnumerable

Multiple items

val int : ‘T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

——————–

type int<‘Measure> = int

Full name: Microsoft.FSharp.Core.int<_>

type: int<‘Measure>
implements: System.IComparable
implements: System.IConvertible
implements: System.IFormattable
implements: System.IComparable<int<‘Measure>>
implements: System.IEquatable<int<‘Measure>>
inherits: System.ValueType

——————–

type int = int32

Full name: Microsoft.FSharp.Core.int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Multiple items

val seq : seq<‘T> -> seq<‘T>

Full name: Microsoft.FSharp.Core.Operators.seq

——————–

type seq<‘T> = System.Collections.Generic.IEnumerable<‘T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<‘T>
inherits: System.Collections.IEnumerable

val sum : seq<‘T> -> ‘T (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sum

val eb2 : Euler1Builder2

Full name: Untitled.eb2

val pe1_eb2 : int -> int

Full name: Untitled.pe1_eb2

val limit : int

type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType

Instead of being like the fold example, this is much more like pipeline.  The only downside here is that the computation expression attempts to be as generic as possible and so we need a type annotation to make the example compile.  Overall, I think it ended up looking quite nice.  It’s also not nearly as complex as you might think.

Let me explain how each of the members of the computation expression fit together to make this work.  The builder’s For method allows us to use a for loop within our expression.  The values generated by that for loop are provided to the For method in the form of a sequence.  When For is called, it is passed that sequence along with a function which does whatever is scoped inside of our expression’s for loop.  In this case, that function is the builder’s Yield method because we are yielding each value.  Finally, the entire computation is preformed within the context of the Run method, which allows the input and output of the expression to be manipulated.  So, within our example we generate our values with For, filter them in Yield and then finally sum them in Run.

I hope you’ve enjoyed our journey through the different styles of computation in F#. The only style I think I didn’t cover here is continuation passing, which is more of a hack to get around the limits of recursion and linked lists anyway.  If you do think of something I missed, want to discuss something related or just feel like being friendly I hope you’ll leave a comment.


02
Feb 11

F# Code and Slides to Share

As I mentioned in my most recent edition of F# Discoveries This Week, it’s Code Camp season and it would be great to see more F# users out there sharing the love.  To help out, I’ve provided the slides from my previous talks in one place under the Creative Commons Attribution license.  I even left all of my slide notes intact.  Do anything you want with them, but please do it in the spirit of spreading F#.

Of course, this applies only to my own slides and code.  Everything made by someone else maintains its existing license.  Duh.

As evidenced by this picture of Don Syme, speaking on F# is guaranteed to make you look at least 200% more awesome

F# and You!

This was my go-to intro to F# talk for almost two years.  It’s a whirlwind tour through F# with an emphasis on conveying why F# is good over how to use it or how it works.  I’ve given variations of this talk over 10 times, and it’s always a crowd pleaser.

Functional Language Paradigms in F#

I gave this talk at the NYC ALT.NET Group shortly before moving to NYC.  It may just be my most well received talk of all time.  If you use this, you’ll need to switch up the questions so people can’t just look up the answers online beforehand.

F# For Testing and Analysis

This talk is an overview of some of the tools available for F# and how to use them.  It’s one of my favorite talks for intermediate F# users.  FsCheck always blows the minds of those who are engineering-minded.

A Lap Around the F# Ecosystem

While similar to F# for Testing and Analysis, this talk focuses on some great tools not involved in testing.  For example, I give FAKE some love.

F# 2.0 – A Day at the Beach

This is the content for my CUFP tutorial.  Giving this talk involved a ton of answering questions and walking around helping directly.  The code is a bit dated, I have a much more recent Silverlight version you can use instead.

F# in the Lab and the Classroom

This was my first attempt at spreading F# in academia and I think it went much better than I expected.  My favorite part is the comparison of a pseudo decision tree with F#’s match statement.

Love the Lambda

This talk is a bit of an unfinished project.  The basic idea is that F# allows you to implement features that would requite compiler changes in languages like C# and VB.NET.  I’ve given it only once with mixed results, but I think it has a lot of potential.

I’ve given a few others but they’ve either been composites of what I posted here or are so old that none of the samples would work now.  I hope that by providing these here I’ve inspired at least one other person to get out there and share the F# love.

I’d love to hear about how you used these slides or answer any questions you might have.  The best way to get in touch is with twitter.


14
Dec 10

I got 99 problems but dynamic ain’t one

If you got runtime errors I feel bad for you son
I got 99 problems but dynamic ain’t one

I got the cube patrol on the code patrol
Foes that wanna try and keep my source out of control
Ruby writers that say he’s “Science Strict Not-Bold”
I’m from university stupid what type of facts are those

If you grew up with segfaults in your joes
You’d celebrate the minute you was havin’ stable codes
I’m like avoid Python it can’t handle my whole payload
If you don’t trust my types you can take my tests off hold

Got beef with podcasts if Iron’s on they show
When those brakepoints hit they don’t know what’s missed
Soft’ mags try an’ ignore my syntax
So readers can buy more tools from ads…

I don’t know how you be writin’ that
without understanding the power that type systems have
I’m from calls to lambdas dude, I ain’t dumb
I got 99 problems but dynamic ain’t one
Hit me

99 problems but dynamic ain’t one
If you got runtime errors I feel bad for you son
I got 99 problems but dynamic ain’t one
Hit me


11
Dec 10

An F# Ant Colony Simulation in Silverlight 4.0 with Dynamic AI Loading

I’ve been enviously watching Phillip Trelford publish excellent F# games all week and tonight I just couldn’t stand it anymore.  I stayed in, rolled up my sleeves and ported the very same ant colony simulation I used in my CUFP workshop to Silverlight 4.0.

Install Microsoft Silverlight

Wow, just look at those little guys go at it.  Silverlight sure is pretty!

As you might have noticed by the big white “Click To Load Custom AI” message, you can also compile your own AI and battle it out with what I’ve included here.  To make things easy I’ve provided a ready to go solution.  Simply load it up, compile it and select the compiled DLL.

Once you’ve loaded your AI the game will immediately start.  Best of luck to you against my little monsters, so far they’ve been undefeated.  If you happen to come up with an ant-dominating example I hope you’ll post it here in the comments.  There were some really creative ideas in the CUFP workshop and I’d love to see what could be done with more than just four hours.

If your interested in the gory details of the simulation itself, I’ve put up a github repository with the entirety of the code.  And just in case you’re wondering, I’m still planning on running that contest.  Expect a ton of cool new AI features and a big focus on combat.

Cheers!

Update:  I’ve mucked with a few things.  Mainly, it will be a bit nicer when handling AI exceptions now.  While I was at it I tweaked some of the game world parameters and so you’ll need to re-download the example solution if you already have it.


01
Dec 10

In Retrospect: The F# in Education Workshop

I was taking the elevator down after getting settled in my hotel room and as the doors opened I was awestruck by the sight of Don Syme sitting on a couch, typing away on his laptop. With a bit of trepidation I walked up to him and introduced myself.  It was immediately obvious that he was both a very friendly fellow and very excited about something in particular.

Don turned his laptop to me and said “look at this”. It was a blog post detailing the release of F# under the Apache 2.0 license. Needless to say, my mind was blown. I was dumbstruck.

Don Syme announcing to the world that F# would forever be under the Apache 2.0 license. (Photo courtesy of Migel de Icaza)

We then proceeded to dinner in the hotel restaurant. Miguel de Icaza was there, and if you know Miguel you know he’s the life of the party. He became even more animated when told about F# becoming open source and pledged to get the source integrated into Mono as soon as possible.

Later that night the Hotel turned into some kind of giant dance party and fashion show.  Thinking of the day ahead we all returned to our rooms.  I did sneak back down later though to grab a celebratory book-publishing nightcap with Ted Neward.  It’s old hat for him, but I’m still reeling from it.

Announcing Professional F# 2.0! (Click for Video)

To be honest, I was a bit intimidated by the idea of speaking to a room full of PhDs. Because of this, I put far more thought and practice into this 30-minute presentation than any of the much longer talks I had given before. Having my material down pat, I was able to turn that anxiety into gusto with what I feel was great success.

While presenting I noticed that the entire room was laughing at my jokes at first but by the end most seemed rather serious.  I took this to mean that many were offended by my critique of current teaching techniques. Had I been too heavy handed with my language?

Afterward my fears were allayed by the enthusiasm of those who came and spoke with me. Later, a swath of positive reviews confirmed that, while I may have been skirting the edge, I hadn’t gone too far.  Even so, I think I’ll try to be a bit softer in my approach in the future.  As they say, you attract more flies with honey than with vinegar.

Judith Bishop
Queen of Microsoft Research

Miguel de Icaza
Lord of all things Mono

Tomas Petricek
F# Jedi

Joe Pamer
Tamer of F# Compiler Lions

Photos Courtesy of Microsoft Research

That night I had dinner and drinks with some of the most brilliant people. Conversation ranged from type systems to the future of F# and Mono. I ended up staying up quite late talking with Tomas about his future plans. It looks as though he has a ton of great stuff for the F# community right on the horizon.

Howard Mansell
The F# Prophet of Credit Suisse

Richard Minerich
Who invited that guy anyway?

Photos Courtesy of Microsoft Research

The next day Howard and I took the train back to New York and discussed our plans for NYC-wide F# domination. Howard is almost single-handedly responsible for Credit Suisse’s rise as one of the biggest F# using companies. They now number over 100 F# users strong and continue to grow. Combined, we might just be unstoppable.

All-in-all I’d say that the event was a great success both personally and for F#. In a couple of years we’ll see some of the first big batches of graduates educated in statically typed functional programming. At that point, those the imperative object oriented camp will need to start playing catch-up.


03
Nov 10

An F# Whirlwind

Just under two weeks ago I was packing up my things at Atalasoft and enjoying my last Friday Beer:30 with coworkers and friends.

Moments before I left Atalasoft to seek fame and fortune.

My last Beer-30 at Atalasoft

A lot has changed in these past two weeks. I’ve moved into my Hoboken apartment and (partially) assembled a whole set of IKEA furniture, I’ve gotten started as the first employee at a brand new company called Bayard Rock, and I’ve seen quite a few exciting things happen in my own little F# world.

First, I’ve managed to get a new site up for my F# Discoveries This Week blog series. It’s called F# Central and I hope to do big things with it far beyond the scope of my weekly blog post. Stay tuned.

Second, after a year of blood, sweat and tears Professional F# 2.0 has been released.  I wrote the entirety of Part 3 and worked hard to convey every moment of functional programming epiphany that I experienced while learning F#.  I hope you’ll pick up a copy and let me know what you think.

Third, this Friday I’ll have the great honor of speaking alongside giants such as Don Syme, Tomas Petricek, Judith Bishop, Joe Pamer, and Howard Mansell at the F# in Education workshop. In my talk entitled F# in the classroom and the lab, I’ll be drawing on my own past experiences in order to paint a picture of how F# can be used to improve all aspects of academic life.  Even if you can’t make it in person be sure to watch it via the internet simulcast.

Finally, with the help of my good friends Rachel Appel and Howard Mansell I’ve got everything in place for the first meeting of the New York F# User Group.  I’m getting the feeling that the NYC F# community is about to explode and I hope you’ll be part of it.  Come join us if you’re in the area and help spread the word if you aren’t.