Steve's Tech Talk

F# Symposium Session 1

I’ve been running an F# symposium internally at Atalasoft.  Here is the first session’s notes and the “answers”.

1. Define simple polynomial:

type polynomial =

{ A : double; B : double; C : double; }

How do we evaluate some polynomial p at position x?

How do we get the roots of p?

2. Simple recursive functions – define Member a l

a is a member of a l if and only if

a) The l is not empty

b) a is the same as the front of the l or Member a (everything but the front of l) is true

Show trivial in-built Member f’n

Write Rember a l – Rember returns a new list that l’ such that l’ does not contain any instances of a.

3. Tail recursion – Square roots

Newton’s Method:

Make a guess.

For a certain number of iterations:

Refine the guess (is actually a Taylor series expansion IIRC) in this way:

Write with a for-loop/mutability.

Recast it recursively

4. Hermite polynomials – here is the definition of a Hermite polynomial:

Write Hermite recursively

Write Hermite iteratively

Write Hermite iteratively, tail-recursively

module File1   

open System   

type polynomial =
    { A : double; B : double; C : double; }   

let eval p x =
    (p.A * x * x) + (p.B * x) + p.C   

let root p =
    let discriminant = (p.B * p.B) - (4.0 * p.A * p.C)
    if p.A = 0.0 || discriminant < 0.0 then raise(ArgumentOutOfRangeException("p"))
    else
        let twoA = 2.0 * p.A
        let radical = sqrt(discriminant)
        let plusRoot = (-p.B + radical) / twoA
        let minusRoot = (-p.B - radical) / twoA
        (plusRoot, minusRoot)   

let derivative p =
    { A = 0.0; B = p.A * 2.0; C = p.B }   let derivativeAt p x = eval (derivative p) x   

let rec Member a l =
    match l with
    | [] -> false
    | head :: tail -> if a = head then true else Member a tail   let rec Member1 a l =
    List.exists a l   

let rec rember a l =
    match l with
    | [] -> []
    | head :: tail -> if a = head then rember a tail 
                      else head :: rember a tail   

let MutableNewtonSquareRoot S iterations =
    let mutable guess = S / 2.0
    for i = 0 to (iterations-1) do
        guess <- 0.5 * (guess + (S / guess))
    guess   let NewtonSquareRoot S iterations =
    let rec NewtonWorker guess iterations =
        if iterations <= 0 then guess
        else
            let newguess = 0.5 * (guess + (S / guess))
            NewtonWorker newguess (iterations - 1)
    let roughestimate = S / 2.0
    NewtonWorker roughestimate iterations   

let rec hermite1 x n = 
    match n with
    | 0 -> 1.0
    | 1 -> 2.0*x
    | _ -> (2.0*x*(hermite1 x (n-1))) - ((double (n-1))*(hermite1 x (n-2)))   

let hermite2 x n =
    let mutable prev = 0.0
    let mutable curr = if n = 1 then 2.0 * x else 0.0
    for i = 2 to n do
        let newcurr = (2.0 * x * curr) - ((double i) - 1.0) * prev
        prev <- curr
        curr <- newcurr
    curr