#light

module Seven

let f _ = "yes"                          // p. 104
printfn "%A" (f 34.5, f [])
let f1 [a; _] = a                        // p. 105 
printfn "%A" (f1 ['f';'g']) 
let f2 (x::xs) = x
printfn "%A" (f2 [1;2;3])
let rec fact = function                  // p. 108
   | 0 -> 1                       
   | n -> n*fact(n-1)
printfn "%A" (fact 10) 
let rec fact1 n =                        // alternate version  
  match n with
   | 0 -> 1
   | n -> n*fact1(n-1)
printfn "%A" (fact 10)
let rec reverse = function
   | [] -> []
   | (first::rest) ->
        reverse rest @ [first]
printfn "%A" (reverse [1;2;3])
let x = 1 
let y = 2                         // p. 110
printfn "%A" (x+y)   
  // light syntax
printfn "%A" (x)     
  // OK, x not local
let rec halve = function          // p. 111
   |  []  -> ([], [])
   |  [a] -> ([a], [])
   |  (a::b::cs) ->
         let (x,y) = halve cs
         (a::x, b::y)
printfn "%A" ( halve [1], 
               halve [1;2],
               halve [1;2;3;4;5;6])
let rec merge = function                 // p. 112
   | ([], ys) -> ys
   | (xs, []) -> xs
   | (x::xs, y::ys) ->
       if x<y then x::merge(xs,y::ys)
       else y::merge(x::xs,ys)
printfn "%A" (merge ([2], [1;3]),
      merge ([1;3;4;7;8], [2;3;5;6;10]))
let rec mergeSort = function
   | [] -> []
   | [a] -> [a]
   | theList ->
       let (x,y) = halve theList
       merge(mergeSort x, mergeSort y)
printfn "%A" (mergeSort [4;3;2;1],
      mergeSort [4;2;3;1;5;3;6])