# Phillip Trelford's Array

## POKE 36879,255

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
```

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:

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