Phillip Trelford's Array

POKE 36879,255

Finding least common multiples by prime factorization

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;2;3;5;7]
        for n in 11..2..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)
    
/// 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,xys) ->       
        x,                          // 3
            xys                     // {3^1;3^2}
            |> Seq.map snd          // {1;2}
            |> Seq.max              // 2
    )                               // {2^3;3^2;7^1}
    |> Seq.map (fun (x,y) ->
        pown x y                    // {8;9;7}
    )
    |> Seq.reduce (*)               // 504

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

F# Units of Measure talk at Open Source eXchange III

The Open Source eXchange III was a mini-conference where members of the ALT.NET community talked about their favourite alternative .NET tools that increase programmer productivity. Units of Measure is a cool language feature in F#, developed by Andrew Kennedy, that lets you easily annotate values with units like metres, kilograms or seconds. Then F# type inference kicks in to give you automatic checking of your unit types at design and compile time, but cost you nothing at run time, e.g.

  let gravityOnEarth = 9.8f<m/s^2> // Acceleration

Following a bit of a Apollo 40th Anniversary theme, I presented 3 code samples (attached):

  • Statistics
  • Orbital Mechanics
  • Lunar Lander

Resources:

Further reading:

F# Rope

The ICFP 2009 programming contest starts on Friday 26th June.

Solving the ICFP 2007 contest task required a scalable string implementation, for which a Rope is a good fit, and the SGI C++ library provides as rope<T,alloc>. A Rope is represented as a binary tree with substrings as leaves.

Rope operations:

  • Appending a string involves creating a new branch with the left as the existing rope and the right as the string to add.
  • Truncation involves creating a new leaf substring with a reduced length.   
  • Insertion involves creating a new branch containing a branch with the left side to the insertion index and the string to insert, plus the right side from the insertion index.
  • Deletion involves creating a new branch with a left substring with reduced length and a right substring with an increased index. 
  • Iterating over the Rope’s characters involves recursively visiting the tree’s substrings.
    For performance, the character length of a branch may be stored, and on branch creation a check made for empty nodes. To optimize small appends branches may be reduced to new strings.
    Ropes are useful for manipulation of large strings, for example with a text editor.
    The following is a naive F# Rope, implemented for fun:
type Rope =
    | Sub of string * int * int
    | Concat of Rope * Rope * int    
    static member Empty = 
        Sub(String.Empty,0,0)
    member this.Length = 
        match this with
        | Sub(_,_,l) -> l
        | Concat(_,_,l) -> l        
    static member Create(s:string) = 
        Rope.Create(s, 0, s.Length)
    static member Create(s, i, l) = 
        Sub(s, i, l)
    static member private Create(lhs:Rope,rhs:Rope) =
        match lhs.Length, rhs.Length with        
        | 0,0 -> Rope.Empty
        | 0,n -> rhs
        | n,0 -> lhs
        | n1,n2 -> Concat(lhs,rhs,n1+n2)   
    member this.to_seq() =
        let rec to_seq = function
            | Sub(s,i,l) -> 
                seq { for n=0 to (l-1) do yield (s.Chars(i+n)) done }
            | Concat(lhs,rhs,_) -> 
                Seq.append (to_seq lhs) (to_seq rhs)
        to_seq this    
    override this.ToString() =
        let builder = System.Text.StringBuilder(this.Length)
        let rec toString = function
            | Sub(s,i,l) -> builder.Append(s, i, l) |> ignore
            | Concat(lhs,rhs,_) -> toString lhs; toString rhs
        toString this
        builder.ToString()
    member this.Append (s:string) = 
        Concat(this, Rope.Create s, this.Length + s.Length)    
    [<OverloadID("Insert(index,Rope)")>]
    member this.Insert(index,value:Rope) =
        let rec insert pos (rope:Rope) =            
            match rope.Length, rope with
            | n, _ when (pos+n) <= index || (pos) > index ->
                rope            
            | n, Sub(s,i,l) ->
                let lhs = Sub(s,i,max 0 (index-pos))
                let rhs = Sub(s,min (i+l) (i+(index-pos)),
                            max 0 (l-(index-pos)))
                Rope.Create(Rope.Create(lhs,value), rhs)
            | n, Concat(l,r,_) ->
                let n = l.Length
                Rope.Create (insert pos l, insert (pos+n) r)
        insert 0 this
    [<OverloadID("Insert(index,string)")>]
    member this.Insert(index,s:string) = 
        this.Insert(index,Sub(s,0,s.Length))      
    member this.Remove(index,length) =
        let rec remove pos (rope:Rope) =
            match rope.Length, rope with
            | n, _ when (pos + n) <= index || pos >= (index + length) ->
                rope            
            | n, Sub(s,i,l) when pos = index -> 
                Sub(s,i+length, max 0 (l-length))
            | n, Sub(s,i,l) when (pos+l) = (index+length) -> 
                Sub(s,i,max 0 (index-pos))
            | n, Sub(s,i,l) ->
                Rope.Create( 
                    Sub(s,i,max 0 (index-pos)), 
                    Sub(s,min (i+l) (i+(index-pos)+length),
                        max 0 (l-(index-pos)-length)))
            | n, Concat(lhs,rhs,_) -> 
                Rope.Create (
                    remove pos lhs, 
                    remove (pos+lhs.Length) rhs)
        remove 0 this                   
    member this.Item        
        with get (index:int) =
            let rec get pos = function
                | Sub(s,i,l) -> s.[i+index-pos]                   
                | Concat(lhs,rhs,_) -> 
                    if index >= (pos + lhs.Length) then 
                        get (pos+lhs.Length) rhs
                    else 
                        get pos lhs 
            get 0 this                     
    member this.Substring(index:int,length:int) =
        let rec sub pos (rope:Rope) = 
            match rope.Length, rope with            
            | n, Sub(s,i,l) ->                                                    
                let offset = index - pos
                if offset < 0 then     
                    Sub(s, i, min (length+offset) l)    
                else
                    Sub(s, i + offset, min length (l-offset))                                    
            | n, Concat(lhs,rhs,_) ->
                if index >= (pos + lhs.Length) then sub (pos+lhs.Length) rhs
                else
                    if (index+length) < (pos+lhs.Length) then
                        sub pos lhs
                    else
                        Rope.Create (sub pos lhs, sub (pos+lhs.Length) rhs)
        sub 0 this