Phillip Trelford's Array

POKE 36879,255

Functional Programming eXchange 2012

Less than a month to go now until the first FP event of this year – the Functional Programming eXchange at Skills Matter in London on March 16th.

functionalpx-670x180

Robert Pickering has put together another great line up including on the F# side Tomas Petricek on F# 3.0’s Type Providers and Loic Denuziere on F# in large scale web apps. There’s also a good number of talks from members of the Clojure, Scala and Haskell communities.

Rob lists plenty of reasons to come to Functional Programming eXchange 2012, on his blog. The case studies on FP in real world applications look particularly compelling and Scala’s AKKA framework is definitely worth a look. Not forgetting the socializing and inevitable pub outing afterwards…

FP Day Cambridge 2011

FP Day saw talks from luminaries in the Functional Programming world, Simon Peyton-Jones and Don Syme give key notes, with hands-on tutorials and experience reports on F#, Clojure and Haskell sandwiched in the middle. Tomas Petricek and I provided the F# filling, and Zach Bray applied the F# source.

FPDayLogo453x132

Turning to the Functional Side With F#

F# is a multi-paradigm programming language with first-class support for Functional Programming, and ships with Visual Studio 2010. Using a mixture of presentation and practical exercises this session aims to help you:

  • learn how to use F#
  • think in a functional way
  • model problem domains using functional types

Tasks Download: http://tomasp.net/fpday.zip & Code Samples on Github

The morning tasks were based on a Point-of-sale (POS) application.

Domain Model:

namespace Checkout

// Common types

type Code = string
type Name = string
type Price = decimal
type Product = Product of Code * Name * Price
type Quantity = decimal

/// Tender types
type Tender =
  | Cash
  | Card of string
  | Voucher

/// Represents line item
type LineItem = 
  | SaleLineItem of int * Product * Quantity
  | TenderLineItem of Tender * Price
  | CancelLineItem of int

Product lookup:

[<AutoOpen>]
module Products = 
    let products = [
            Product("8717644012208","Lynx Africa",2.49M)
            Product("5010123730215","Listerine",2.49M)
            Product("5000347009242","Aquafresh",1.99M)
            Product("5045094763863","Ibuprofen", 1.99M)]
    let Lookup code = 
        products |> Seq.tryFind (function Product(code',_,_) -> code' = code)

Functions to be implemented in the task:

[<AutoOpen>]
module Lines =
    let saleTotal lines =
        lines |> List.sumBy (fun line ->
            match line with
            | SaleLineItem(id,Product(_,_,price),quantity) -> price*quantity
            | _ -> 0.0M
        )
    let tenderTotal lines =
        raise (new System.NotImplementedException())
    let cancelTotal lines =
        raise (new System.NotImplementedException())

Sale type:

type Sale () =
    let mutable items = []    
    member sale.AddItem (item:LineItem) = items <- item::items
    member sale.TotalAmount = saleTotal items - cancelTotal items
    member sale.OutstandingAmount = sale.TotalAmount - tenderTotal items
    member sale.ChangeDue = 
        if sale.OutstandingAmount < 0M 
        then -sale.OutstandingAmount
        else 0M

Failing tests:

open NUnit.Framework

[<TestFixture>]
module Tests = 
  open System.Diagnostics

  [<Test>]
  let ``Over tendering with cash should give change`` () =
    let sale = Sale()
    let product = Product("123", "3 Pay As you Go", 10.0M)
    sale.AddItem(SaleLineItem(1, product, 1.0M))
    sale.AddItem(TenderLineItem(Cash,20.00M))
    Assert.That(sale.ChangeDue = 10.0M)

  [<Test>]
  let ``Tendering full amount with card should leave no change`` () =
    let sale = Sale()
    let product = Product("123", "3 Pay As you Go", 10.0M)
    sale.AddItem(SaleLineItem(1, product, 1.0M))
    sale.AddItem(TenderLineItem(Card("1234123412341234"), 10.00M))
    Assert.That(sale.ChangeDue = 0.0M)

  [<Test>]
  let ``Cancelled items should not be charged`` () = 
    let sale = Sale()
    let product = Product("123", "3 Pay As you Go", 10.0M)
    sale.AddItem(SaleLineItem(1, product, 1.0M))
    sale.AddItem(CancelLineItem(1))
    Assert.That(sale.OutstandingAmount = 0.0M)

  do
    ``Over tendering with cash should give change`` ()
    ``Tendering full amount with card should leave no change`` ()
    ``Cancelled items should not be charged`` ()

If you'd like to learn more about F#, there are still places left at the Progressive F# Tutorials at Skills Matter in London on November 3-4th:

progfsharp_tutorials

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 .