F# Programming Exercises

exercises.fs

open System

let bigFib n =
    let rec loop previous previousPrevious = function
        | n when n = 0I -> previousPrevious
        | n -> loop (previous + previousPrevious) previous (n - 1I)
    loop 1I 0I n

let factorial n = 
    let rec loop acc = function
        | n when n = 0I -> acc
        | n -> loop (acc * n) (n - 1I)
    loop 1I n

let pair list = 
    let rec loop acc = function
        | [] | [_] -> List.rev(acc)
        | first :: second :: tail -> loop ((first, second)::acc) tail
    loop [] list

let unpair list = 
    let rec loop acc = function
        | [] -> List.rev(acc)
        | (first, second) :: tail -> loop (second :: first :: acc) tail
    loop [] list

let expand list = 
    let rec loop acc = function
        | [] -> List.rev(acc)
        | head :: tail -> loop ((head :: tail) :: acc) tail
    loop [] list

let rec gcd a b = match b with
                    | 0 -> a
                    | n -> gcd b (a % b)

let gcdl x = match x with
                | [] -> 0
                | head :: tail -> List.fold gcd head x

let rec split = function
        | [] -> ([], [])
        | [a] -> ([a], [])
        | first :: second :: tail -> let (r, s) = split tail
                                     (first::r, second::s)

let rec merge = function
        | ([], a) -> a
        | (b, []) -> b
        | (leftHead::leftTail, rightHead::rightTail) -> if leftHead < rightHead then leftHead::merge(leftTail, rightHead::rightTail)
                                                        else rightHead::merge(leftHead::leftTail, rightTail)

let rec mergeSort = function
        | [] -> []
        | [x] -> [x]
        | list -> let left, right = split list
                  merge(mergeSort left, mergeSort right) 

[<EntryPoint>]
let main argv = 
    [0I .. 100I] |> Seq.iter (fun x -> printfn "fib(%O) = %O" x (bigFib x))
    [0I .. 100I] |> Seq.iter (fun x -> printfn "factorial(%O) = %O" x (factorial x))
    printfn "Pair test: %b" (pair [ 1 .. 10 ] = [(1, 2); (3, 4); (5, 6); (7, 8); (9, 10)])
    printfn "Pair test: %b" (pair [ "one"; "two"; "three"; "four"; "five" ] = [("one", "two"); ("three", "four")])
    printfn "Unpair test: %b" (unpair [(1, 2); (3, 4); (5, 6)] =  [1; 2; 3; 4; 5; 6])
    printfn "Unpair test: %b" (unpair [("one", "two"); ("three", "four")] = ["one"; "two"; "three"; "four"])
    printfn "Expand test: %b" (expand [ 1 .. 5 ] = [ [1; 2; 3; 4; 5]; [2; 3; 4; 5]; [3; 4; 5]; [4; 5]; [5] ])
    printfn "gcdl test: %b" (gcdl [15; 75; 20] = 5)
    printfn "Merge sort 5, 2, 8, 3: %A" (mergeSort [5; 2; 8; 3])
    0