Phillip Trelford's Array

POKE 36879,255

F# Talk at Edge UG: Slides and Demos

The Edge UG, based in London, is the “Uber Usergroup for all developers and IT Pros working on the Microsoft technology stacks.” This statement doesn’t seem too wide of the mark either; when put to a show of hands most attendees responded yes to experience of both C++ and C#, with plenty also playing with WPF and Silverlight!

I presented a 1 hour talk introducing F# with 4 demos (attached to this post):

  • Full-screen WPF POS Checkout sample with Barcode scanner integration (in 100 lines)
  • Twitter WPF client script (200 lines)
  • Matermind board game in WPF (300 lines)
  • Lunar Lander XNA game (>400 lines)

Expect a video of the talk should be on the Edge UG site soon.

Some tweet feedback from the event:

ebrucucen:F# session started with @ptrelford at #edgeuk

johanbarnard: Watching really interesting F# presentation by @ptrelford at #EdgeUG.

ptrelford:Talking about F# again in front of a lot of people

ColinMackay: F# is more fun than I expected. Demos use XNA to create games in F#. #edgeug

raybooysen: Lunar lander in XNA and F#! #edgeug

johnno31: @ptrelford when can we have pizza??

My tweet was delivered from the F# Twiiter client script during the talk!

F_ Introduction_EdgeUG.ppsx (660.16 kb)

FSharpDemos.zip (53.40 kb)

P.S. To see more F# related talks please join the new F# London User Group

Sorted with F# custom operators

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):

Team Played Goal Difference Points
Arsenal 22 34 48
Chelsea 21 34 48
Man Utd 22 30 47
Spurs 22 18 38
Man City 21 12 38

 

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.

C++ vs C# vs F# vs Haskell

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

Language Lines of code Performance(ms)
C++ 39 5.213
C# 35 5.332
F# sequence 30 14.075
F# recursive 25 5.412
Haskell 17 ?

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 article has been translated to Serbo-Croatian language by WHGeeks .