F# lets you define your own operators, and like a man with a new hammer hunting for nails :) I’ve found an application of F# custom operators for sorting multiple columns:

let inline (|?) a b = if a = 0 then b else a

Lets start by trying to sort the table position of the current top 5 of English Football’s Premier League (compiled on 2010-01-21):

Lets say we represent the table as an array of tuples:

let table = [|  
        ("Arsenal", 22, 34, 48) 
        ("Chelsea", 21, 34, 48)          
        ("Spurs",   22, 18, 38) 
        ("Man City",21, 12, 38)
        ("Man Utd", 22, 30, 47)
    |] 

If we could just sort on points, and wanted to sort the array in place, we could write:

do  Array.Sort(table, fun (_,_,_,a) (_,_,_,b) -> b - a)   

But as we can see from the table, some of the teams have the same points, so we need to order on points and goal difference. In the case of Arsenal and Chelsea at the top of the table, they not only have the same points, they have the same goal difference. In this situation the custom is to sort alphabetically (lucky for you if your team starts with the letter ‘A’).

The sort function must now apply secondary sorting criteria if the first expression gives zero:

do  Array.Sort(table, fun a b -> 
        let nameA, _, gdA, pointsA = a
        let nameB, _, gdB, pointsB = b
        let points = pointsB - pointsA
        let gd = gdB - gdA
        let names = String.Compare(nameA, nameB)
        if points <> 0 then points
        else if gd <> 0 then gd
        else names
    )  

) 

Now the custom operator introduced at the start of the article really captures it:

do  Array.Sort(table, fun a b -> 
        let nameA, _, gdA, pointsA = a
        let nameB, _, gdB, pointsB = b
        pointsB - pointsA |? gdB - gdA |? String.Compare(nameA, nameB)                
    )  

The beauty of using the custom operator here, say over a function, is operators can be placed between expressions so can be used to compose the sort.

Finally, there are however a couple of other ways to hammer this nail:

• sort by mapping the table entry tuple
• using LINQ OrderBy and ThenBy

Mapping the table entry is easy on the eye but it does require the generation of temporary tuples and a new array:

do  table |> Array.sortBy (fun (name,_,gd,points) -> -points,-gd,name) 

Using LINQ is also pretty easy on the eye but requires the generation of a new sequence:

do  table.OrderByDescending(fun (_,_,_,p) -> p)
        .ThenByDescending(fun (_,_,gd,_) -> gd)
        .ThenBy(fun (name,_,_,_) -> name)

PS If you are looking for a similar pattern in C#, Jon Skeet shows a similar (but more verbose) way of composing sort expressions using the ?? operator in his C# in Depth book.

PPS Tomas Petricek has a nice article with some sample use of custom operators in F#. Coincidentally he has just authored a book with Mr Skeet on Functional Programming.

PPPS For clarity I should point out that I am a Man Utd supporter, so the timing for this article could be seen as somewhat unfortunate.

Since I first posted an F# solution to Left-Truncatable Primes, C# and Haskell have entered the frame, and although this is not a good problem for a serious comparison of languages, I think it is still interesting.

So lets start at the beginning, Dominic Penfold initially posed the problem and gave an efficient algorithm implemented in C++ (39 lines):

bool IsPrime(int num)
{
    int sqrt = 1 + sqrtf(num);
    for (int i=2; i<sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}
 
int NthLeftTruncatablePrime(int target)
{
    std::vector<int> PrimeRoots;
    PrimeRoots.push_back(2);
    PrimeRoots.push_back(3);
    PrimeRoots.push_back(5);
    PrimeRoots.push_back(7);
    int start = 0;
    int tens = 10;    
    while(true)
    {
        int end = PrimeRoots.size();
        for (int i=1; i<10; i++)
        {
            for (int pos = start; pos< end; pos++)
            {
                int newprime = tens * i + PrimeRoots[pos];
                if (IsPrime(newprime))
                {
                    PrimeRoots.push_back(newprime);
                    if (PrimeRoots.size()==target)                                      
                        return newprime;                    
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

Performance was considerably faster when 32-bit integers were switched for 64-bit integers.

The C++ code is very easily converted into C# (35 lines):

static bool IsPrime(int num)
{
    int sqrt = 1 + (int ) System.Math.Sqrt(num);
    blue">for (int i = 2; i < sqrt; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

static int NthLeftTruncatedPrime(int target)
{
    var primeRoots = new List<int>() { 2, 3, 5, 7};               
    int start = 0;
    int tens = 10;
    while (true)
    {
        int end = primeRoots.Count;
        for (int i = 1; i < 10; i++)
        {
            for (int pos = start; pos < end; pos++)
            {
                int newprime = tens * i + primeRoots[pos];
                if (IsPrime(newprime))
                {
                    primeRoots.Add(newprime);
                    if (primeRoots.Count == target)
                        return newprime;
                }
            }
        }
        start = end;
        tens *= 10;
    }
}

Conversion to F# is only slightly trickier as there is no equivalent return statement, but similar behavior can be accomplished using yield (30 lines):

let IsPrime n =
    if n = 1 then false
    else    
        let max = n |> float |> sqrt |> int
        let rec Test = function
            | x when x > max -> true
            | x -> if (n % x) = 0 then false else Test (x+1)
        Test 2

let NthLeftTruncatablePrime n =
    let oneDigitPrimes = [2;3;5;7]          
    seq {            
        let primes = ref oneDigitPrimes        
        for tens = 1 to 8 do
            let acc = ref []
            for i=1 to 9 do 
                let newPrime = i * pown 10 tens                
                let primes' = ref !primes
                while (!primes').Length > 0 do                            
                    let x = newPrime+(!primes').Head
                    if IsPrime x then 
                        acc := x :: !acc
                        yield x
                    primes' := (!primes').Tail                    
                done                                     
            done         
            primes := !acc |> List.rev    
        done            
    }
    |> Seq.append oneDigitPrimes
    |> Seq.nth (n-1)

The extra overhead of generating a sequence can be avoided using instead recursion (25 lines including IsPrime function):

let NthLeftTruncatablePrime index =
    let rec Find digit factor primes primes' count acc =
        match digit, primes' with
        | 10, _ -> 
            let primes = List.rev acc
            Find 1 (10*factor) primes primes count []
        | _, [] ->
            Find (digit+1) factor primes primes count acc
        | _, prime::tail -> 
            let k = (digit * factor) + prime
            let count, acc =
                if IsPrime k then count+1, k::acc else count, acc 
            if count = index then k
            else Find digit factor primes tail count acc
    let primes = [2;3;5;7]
    if index <= 4 then List.nth primes (index-1)
    else Find 1 10 primes primes 4 []

Later Matt Curran (coincidentally another ex-games developer) got in on the act with a Haskell version (17 lines including a comment – although the lines are a little dense):

isPrime :: Int -> Bool
isPrime 1 = False
isPrime x = null $ take 1 [n | n <- [2..upperBound x], 0 == mod x n]
    where
        upperBound = floor . sqrt . fromIntegral

-- list of all left truncatable primes
ltps :: [Int]
ltps = ps 1 [0]
    where
        ps _ []      = []
        ps m prevMag = thisMag ++ (ps (m*10) thisMag)
            where
                thisMag = primes [x*m | x <- [1..9]] prevMag
                    where
                        primes [] _ = []
                        primes (m:mgs) bases = 
                            (filter isPrime [m+x | x <- bases]) ++ (primes mgs bases)

Results Breakdown by language

Note: the time is to generate the 1000th prime, and the same computer was used for all tests, as was release mode. Haskell time coming soon.

LeftTruncatablePrime.cpp (1.45 kb)

LeftTruncatablePrime.cs (1.58 kb)

LeftTruncatablePrime_seq.fs (1.53 kb)

LeftTruncatablePrime_rec.fs (1.36 kb)

This week in the Software Architecture evening course I’m giving for non-developers the topic was UML Sequence Diagrams. The class task was to create a basic sequence diagram for behaviour of an Auction house, and here are the results from the class, watch out e-bay ;)

Yesterday a colleague asked me how a function to calculate the nth left-truncatable prime might look in F# for comparison against a C++ implementation, so lets start with the definition from Wikipedia:

In number theory, a left-truncatable prime is a prime number which, in a given base, contains no 0, and if the leading ("left") digit is successively removed, then all resulting numbers are prime. For example 9137, since 9137, 137, 37 and 7 are all prime. Decimal representation is often assumed and always used in this article.

The following is the F# implementation, using recursion, coded up on the train home last night (the function takes about 5ms to calculate the 1000th left-truncatable prime, just 2ms off very close to the optimized C++ time):

let IsPrime n =
    if n = 1 then false
    else    
        let max = n |> float |> sqrt |> int
        let rec Test = function
            | x when x > max -> true
            | x -> if (n % x) = 0 then false else Test (x+1)
        Test 2
 
let NthLeftTruncatedPrime index =
    let rec Find digit factor primes primes' count acc =
        match digit, primes' with
        | 10, _ -> 
            let primes = List.rev acc
            Find 1 (10*factor) primes primes count []
        | _, [] ->
            Find (digit+1) factor primes primes count acc
        | _, prime::tail -> 
            let k = (digit * factor) + prime
            let count, acc =
                if IsPrime k then count+1, k::acc else count, acc 
            if count = index then k
            else Find digit factor primes tail count acc
    let primes = [2;3;5;7]
    if index <= 4 then List.nth primes (index-1)
    else Find 1 10 primes primes 4 []

Initially the comparison was intended to be simply on readability, where the F# code was unsurprisingly found to be shorter, and the imperative style (lots of for loops) of the C++ code more familiar to some.

Just out of curiosity I ran a quick performance check to see whether performance was in the same order of magnitude, fully expecting the C++ to faster. In fact initially the C++ was half the speed of the F# code (i.e. the C++ took twice as long). After a little head scratching, I tried a few teaks on the C++, for example giving the STL vector an initial capacity which increased performance by about 20%. Then I spotted that the C++ was using Int64 underneath and the F# Int32. Making the C++ use Int32 brought comparable performance to the F# code give or take a millisecond. At no point did I bother trying to optimize the F# code (except for running the function once before doing the timing to ensure the code had been just-in-time (JIT) compiled).

At the time of first posting this entry it was thought that the C++ was a couple of milliseconds faster. Actually later in the day it was found that there was an error in the calculation of the C++ result and in fact there was no discernable difference between the performance of the C++ and F# code. There are further algorithmic optimizations that could be applied to both implementations but I will leave that as an exercise for the reader.

This is quite interesting, it really does show that you can *NOT* assume that writing code in unmanaged C++ will intrinsically make it faster than code written in managed languages like C# and F#.

Its the 3rd of 7 weekly instalments of a Software Architecture evening course I’m giving for 20 or so non-developers. So far each session has been split in two with a half hour of lecture and a half hour workshop. For the workshop the class is split into teams of 3, 4 or 5 and given a task to solve with UML:

• Week 1: Use Cases for an Auction system
• Week 2: Class Diagrams for an Auction system
• Week 3: Class Diagrams for an Exchange

Each team presented their diagram to the class, and here are the results for this week -developers better beware. ;)

The F# Power Pack includes an arbitrarily large Rational type called BigNum, which in turn uses the arbitrarily large BigInt type for the numerator and denominator. The BigInteger type has recently moved into .Net 4.0 under the System.Numerics namespace, It would be nice if BigNum could join it there.

What if you want a fixed size Rational implementation that can be used from any .Net language? The following is a sample F# implementation using Int64 for the numerator and denominator values:

open System

type Rational64 (numerator:Int64,denominator:Int64) =
    do if denominator = 0L && numerator <> 0L then
        raise (new DivideByZeroException())
    let rec gcd x y =    
        match y with
        | 0L -> x
        | _ -> gcd y (x % y)
    let norm =
        let u = int64 (sign denominator) * numerator
        let v = abs denominator     
        let d = gcd (abs u) v     
        if denominator <> 0L then u / d, v / d
        else numerator, denominator
    let numerator, denominator = norm    
    static let zero = Rational64(0L,1L)
    static let Op f (a:Rational64,b:Rational64) = 
        let x,y = a.Numerator, a.Denominator
        let u,v = b.Numerator, b.Denominator
        f x y u v
    static let Add = Op (fun x y u v -> new Rational64(x * v + u * y, y * v))
    static let Sub = Op (fun x y u v -> new Rational64(x * v - u * y, y * v))
    static let Mul = Op (fun x y u v -> new Rational64(x * u, y * v))
    static let Div = Op (fun x y u v -> new Rational64(x * v, y * u))        
    static let Eq = Op (fun x y u v -> x * v = u * y)
    static let Lt = Op (fun x y u v -> x * v < u * y)
    static let Le = Op (fun x y u v -> x * v <= u * y)
    static let Gt = Op (fun x y u v -> x * v > u * y)
    static let Ge = Op (fun x y u v -> x * v >= u * y)
    static let Compare (a:Rational64,b:Rational64) =
        if Lt (a,b) then -1
        else if Gt (a,b) then 1
        else 0
    new(numerator:Int64) = Rational64(numerator,1L)                  
    member this.Numerator = numerator 
    member this.Denominator = denominator
    static member Zero = zero
    member this.ToDecimal() =
        decimal this.Numerator / decimal this.Denominator
    member this.ToDouble() =
        double this.Numerator / double this.Denominator
    override this.ToString() =
        match numerator, denominator with
        | n, 1L -> n.ToString()
        | n, d -> sprintf "%d/%d" n d                             
    static member ( + ) (a,b) = Add (a,b)
    static member ( - ) (a,b) = Sub (a,b)
    static member ( * ) (a,b) = Mul (a,b)
    static member ( / ) (a,b) = Div (a,b)
    static member op_Equality (a,b) = Eq (a,b)
    static member op_Inequality (a,b) = not (Eq (a,b))
    static member op_LessThan (a,b) = Lt (a,b)
    static member op_LessThanOrEqual (a,b) = Le (a,b)
    static member op_GreaterThan (a,b) = Gt (a,b)
    static member op_GreaterThanOrEqual (a,b) = Ge (a,b)
    interface IComparable with
        member this.CompareTo (x) = Compare (this, x :?> Rational64)                 
    static member Equals(a,b) = Eq(a,b)
    override this.Equals x = this = (x :?> Rational64) 

Finally specific for F# by implementing a NumericLiteralX module it is possible to declare Rational64 literals like so (Q for Quotient):

module NumericLiteralQ =
    let FromZero () = Rational64(0L)
    let FromOne () = Rational64(1L)
    let FromInt32 (x) = Rational64(int64 x) 
    let FromInt64 (x:Int64) = Rational64(x) 

module Test = 
    let x = 42Q

Rational64.fs (4.90 kb)

Rational64Test.cs (4.74 kb)

On Sunday, I thought I’d try and show my son the fun side of programming and Logo seemed a good place to start. Using a Logo Interpreter written in JavaScript, in seconds we were drawing pentagons.

to pentagon repeat 5 [ fd 100 rt 72 ] end

That jogged my memory to a cool sample Logo Interpreter written by Adam Granicz in less than 400 lines, posted on HubFS back in 2006. The code didn’t run straight away due to some subtle changes in the language, but after some worthwhile coercion I was able to resurrect the code, which I have attached.

Try executing:

canvas 300 300
to pentagon :x repeat 5 [ fd :x rt 72 ]
pentagon 100

canvas 400 500
to spiral :x repeat :x [fd 4 lt * repcount 1.1]
spiral 10000

Logo.zip (5.80 kb)

For the last 2 days I’ve been attending the Software Architect 2009 conference located at the iconic Royal College of Physicians building opposite Regent's Park in central London. Overall the events have been interesting, that said, the content has not in general been particularly new or ground breaking, but that is probably the nature of the discipline. It has however been good to be reminded of key principles, to listen to the views of others, and as always I’ve found it quite thought provoking. For each talk I attended I’ve created an entry on Twitter @ptrelford:

Tim Ewald on Saving Software Architecture: "When you go too far up, abstraction-wise, you run out of oxygen" Joel on Architecture Astronauts

Kevin Seal on MorganDirect's client-side architecture: Swing app with Eclipse IDE look, blackboard pattern, detailed logs & takes screenshots

Kevlin Henney on Slicing design over time: take time estimate & half it, coding is performance art so practice, test cases are propositions.

Dave Wheeler on Coding a solid UI: "WPF is great", dependency properties are cool, do MVVM pattern, get an HCI expert & use Expression Blend

Richard Blewett on What's New in WF 4.0: Everything. Complete API rewrite. 3.5 favoured code based workflow. 4.0 declarative XAML is king.

Dino Esposito asks "How good are you at .NET software design?" Separation of concerns, OOD principles - prefer composition to inheritance etc

Kevlin Henney on Modelling in the age of agility: Most important aspect of modelling is the -ing, i.e. the social and collaborative aspects.

Simon Brown on "Documenting your software architecture - why and how?" Start with a context and set the scene. Put yourself in others shoes.

Most popular analogy: Construction (Tim Ewald & Kevlin Henney)

Favourite example: Fast-Track Construction of the Empire State Building (Kevlin Henney)

Best term usage: idempotent (Simon Brown)

Best vocabularly usage: pontificate (Kevlin Henney)

Only search term suggestion: Death by UML Fever (Kevlin Henney again)

Least Common Multiple on Wikipedia.

How well can the prime factorization method be expressed in F#? This is my first solution and just for fun:

open System
 
/// Generate sequence of all integer primes
let primes =
    let isPrime x =
        let rec test = function
            | 1 -> true
            | n -> if x % n = 0 then false else test (n-1)
        test (x/2)
    seq {        
        yield 1
        yield 2
        yield 3
        yield 5
        yield 7        
        for n = 11 to Int32.MaxValue do
            if isPrime n then yield n
        done
    }

/// Compute prime factors
/// <returns>
/// Sequence of prime number powers (x^y) as tuple of (x,y)
/// </returns>
let primefactors x =
    /// Compute prime factor
    let primefactor x =
        primes
        |> Seq.skip 1
        |> Seq.takeWhile (fun prime -> prime <= x)
        |> Seq.tryFind (fun prime -> (x % prime) = 0)
    /// Compute list of prime factors 
    let rec fold acc x =
        match primefactor x with
        | Some factor -> fold (factor::acc) (x/factor)
        | None -> acc
    fold [] x           
    |> Seq.countBy (fun x -> x)    
    
/// Raise x to power of y
let pow (x,y) = 
    let rec fold acc = function       
        | 0 -> acc
        | n -> fold (acc*x) (n-1)
    if y >= 0 then fold 1 y
    else 1 / (fold 1 (-y))
        

/// Compute lowest common multiple    
let lcm xs =       
    xs                              // {8;9;21}
    |> Seq.map primefactors         // {{2^3};{3^2};{3^1;7^1}}
    |> Seq.concat                   // {2^3;3^2;3^1;7^1}
    |> Seq.groupBy (fun (x,y) -> x) // {{2;{2^3}};{3;{3^1;3^2}};{7;{7^1}}}
    |> Seq.map (fun (x,xs) ->       
        x,                          // 3
        xs                          // {3^1;3^2}
        |> Seq.map snd              // {1;2}
        |> Seq.max                  // 2
    )                               // {2^3;3^2;7^1}
    |> Seq.map pow                  // {8;9;7}
    |> Seq.reduce (*)               // 504

           
do  lcm [8;9;21] |> printf "%d" // yields 504

The .Net Framework ships with a C# code compiler that lets you generate in-memory assemblies. This can be used to run C# scripts without the need for the installation of a large application like PowerShell. The following code, which targets .Net 2.0, builds into a 7K executable, and is all that is needed to run C# source files from the command line:

using System;
using System.CodeDom.Compiler;
using System.Collections.Specialized;
using System.Diagnostics;
using System.IO;
using System.Text.RegularExpressions;
using Microsoft.CSharp;
using System.Collections.Generic;

static class Program
{
    /// <summary>
    /// Executes specified C# script file
    /// </summary>
    /// <param name="args">Path of C# script file</param>
    static void Main(string[] args)
    {
        // Check parameters
        if (args.Length == 0)
        {
            Console.WriteLine("Please specify a C# script file");
            Environment.Exit(-1);
        }
        // First parameter is source file path
        string path = args[0];
        // Check file exists 
        if (!File.Exists(path))
        {            
            Console.WriteLine("Specified file does not exist");            
            Environment.Exit(-1); 
        }
        // Read source from file
        string source = ReadFile(path);
        // Initialize compiler options
        CompilerParameters compilerParameters = 
            new CompilerParameters();      
        compilerParameters.GenerateExecutable = true;
        compilerParameters.GenerateInMemory = true;
        compilerParameters.TreatWarningsAsErrors = true;
        compilerParameters.CompilerOptions = "/nowarn:1633"; // unrecognized pragmas
        // Prepass source for #pragma reference statements        
        StringReader reader = new StringReader(source);       
        while (true)
        {
            string line = reader.ReadLine();
            if (line == null) break;            
            string pattern = 
                "\\s*#pragma\\s+reference\\s+\"(?<path>[^\"]*)\"\\s*";
            Match match = Regex.Match(line, pattern);                   
            if (match.Success)            
                compilerParameters.ReferencedAssemblies.Add
                    (match.Groups["path"].Value);            
        }
        // Specify .NET version
        Dictionary<string, string> providerOptions =
            new Dictionary<string, string>();
        providerOptions.Add("CompilerVersion", "v3.5");
        CSharpCodeProvider provider = new CSharpCodeProvider(providerOptions); 
        // Compile source           
        CompilerResults results =
                provider.CompileAssemblyFromSource(
                    compilerParameters,
                    new string[] { source });
        // Show errors
        if (results.Errors.HasErrors)
        {
            Console.WriteLine("Errors Building " + path);
            foreach (var err in results.Errors)
                Console.WriteLine(err);
            Environment.Exit(-1);
        }
        // Extract argument tail
        string[] parameters = new string[args.Length - 1];
        Array.Copy(args, 1, parameters, 0, args.Length-1);
        // Invoke compiled assembly's entry point
        results.CompiledAssembly.EntryPoint.Invoke
            (null, new object[1] { parameters });        
    }
    
    private static string ReadFile(string path)
    {
        using (StreamReader reader = File.OpenText(path))
            return reader.ReadToEnd();
    }
}

Script files look just like Console applications:

using System;

public class Class1
{
    static void Main(string[] args)
    {
        Console.WriteLine("Hello World");
    }
}

Finally additional assemblies can be referenced using #pragma directives:

#pragma warning disable 1633 // disable unrecognized pragma directive warning
#pragma reference "System.Windows.Forms.dll"

using System.Windows.Forms;

public class Class1
{
    static void Main(string[] args)
    {
        MessageBox.Show("Hello World");
    }
}