// 4.2
let rec sumI a m = function
     0 -> a
   | n -> sumI (a+m+n) m (n-1)

// Helper for simple calls to iterative function
let sum m = sumI m m

// 4.3
let rec listlenI a = function
     [] -> a
   | x::xs -> listlenI (a+1) xs

// Helper
let listlen l = listlenI 0 l

// 5.4
let rec factA = function
    | (0, m) -> m
    | (n, m) -> factA(n-1, n*m)

let rec factC c = function
    | 0 -> c 1
    | n -> factC (fun inp -> c(n*inp)) (n-1)

// Timing results (for n=10^7):
// factA -> 0.088s
// factB -> 1.008s
// disclaimer: obviously I didn't get any meaningful results from these runs

// 5.5
let fib n =
    let mutable a = 1
    let mutable b = 1
    let mutable rn = n-2
    while rn > 0 do
        (
        let tmp = b
        b <- a+b
        a <- tmp
        rn <- rn - 1
        )
    b

// 4.6
// iterative
let rec fibA n1 n2 = function
      2 -> n2
    | n -> fibA n2 (n1+n2) (n-1)

// continuation
let rec fibC n c = match n with
      1 -> c 1
    | 2 -> c 1
    | n -> fibC (n-2) (fun v -> fibC(n-1) (fun v2 -> c(v+v2)))

// Timing results (using n=40):
// fibA -> 0s
// fibC -> 6.031s
// while -> 0s

type BinTree<'a> = | Leaf
                   | Node of BinTree<'a> * 'a * BinTree<'a>

// 4.7
let rec countA a t =
    match t with
    | Leaf              -> a
    | Node(tl, n, tr)   -> countA (a+(countA (1) tr)) tl

// 4.8
let rec countAC t a c =
    match t with
    | Leaf              -> c (a)
    | Node(tl, n, tr)   -> countAC tl (1) (fun v -> countAC tr (a+v) c)

// 4.9?
let rec bigListK n k =
    if n=0 then k []
    else bigListK (n-1) (fun res -> 1::k(res))

// 4.10
let rec leftTree s a = function
    | 0 -> a
    | n -> leftTree s (Node(a, s-n, Leaf)) (n-1)

let rec rightTree s a = function
    | 0 -> a
    | n -> rightTree s (Node(Leaf, s-n, a)) (n-1)

// From the book
let rec countC t c =
    match t with
    | Leaf -> c 0
    | Node(tl,n,tr) ->
        countC tl (fun vl -> countC tr (fun vr -> c(vl+vr+1)))

let rec count = function
    | Leaf -> 0
    | Node(tl,n,tr) -> count tl + count tr + 1

// count  (leftTree)  -> OutOfMemoryException at 10^5 nodes
// countA (leftTree)  -> OutOfMemoryException at 10^8 nodes
// count  (rightTree) -> OutOfMemoryException at 10^5 nodes
// countA (rightTree) -> OutOfMemoryException at 10^5 nodes

// Timing: n=10^7
// countAC (leftTree)  -> 2.274s
// countAC (rightTree) -> 1.423s
// countC  (leftTree)  -> 2.719s
// countC  (rightTree) -> 2.924s

// 4.11
let odd = Seq.initInfinite (fun i -> i*2+1)

// 4.12
let rec fact = seq {
    yield 1
    yield! Seq.map2 (*) fact (Seq.initInfinite (fun i -> i+1))
}