// Misc. features in F#/OCAML

open System

// Typed Lambda Terms

let I = fun x -> x;;
let K = fun x -> fun y -> x;;
Console.WriteLine("type of K: "+string(K));; 

// curried and non-curried functions:

let f x y = x + y;;
let g(x,y) = x+y;;

let mutable x = 4;;
x <- x+1;;  // assignment,  = means boolean equality or definition
printf "%d\n" x;
printf "%d\n" (g (1,2));; // not extra () around g because printf is curried

// mutable arrays
let a = [|5;3;4;1;8;2|];; 
// length is a.Length, compatible with C#, other .Net languages

a.[1] <- 2 * a.[1];
Console.WriteLine(a);
for x in a do
  printf "%d " x;;

// lists
let b = [2;3;4];;  // must use ; - using , will make a tuple

let b2 =          
  match b with
    | (h::t) -> h       // :: is cons, [] is empty list 
    | _ -> b.[1];;


for i = 1 to 10 do
  printfn "%d" i;;


// let:

let x = 2 in let y=3 in printfn "%d" (x+y);;   // note ()s around x+y
// or use indentation like in Python.

// binary search in F#  (some type annotation required)
let bsearch(x, A:'a [] when 'a:comparison) = 
   let mutable starti,endi = 0,A.Length-1
   let mutable answer = false 
   while starti<=endi && not(answer) do
      let mid = (starti+endi)/2;
      match A.[mid] with
        | u when u=x -> answer<-true;
        | u when x<u -> endi <- mid-1;
        | _ -> starti<-mid+1;
   answer;;    // note the use of indentation to end while loop, like in python

let A = [|2;4;6;8|];
Console.WriteLine( bsearch(4,A) );;
Console.WriteLine( bsearch(3,A) );;

// what about implicit pointers?
// bubblesort in F#
let mutable sort = fun (a: 't [] when 't:comparison) -> 
  let n = a.Length in  
    for i = 0 to n-2 do   // bubblesort
      for j = 0 to n-2-i do
         if a.[j] > a.[j+1] then
            let temp = a.[j] in 
               a.[j] <- a.[j+1];
               a.[j+1] <- temp;
         else ();;     // () is nop, of type "unit" (void)
// end of bubblesort function


// assign sort to a better sorting function (quicksort)
sort <- fun(A:'a[]) ->    // expect compiler warning (ignore) from type inf.
  let mutable stack = [(0,A.Length)] // don't implement quicksort recursively
  let mutable i,k = 0,0  //index vars
  let mutable si,en = 0,A.Length  // start and end of partition
  let mutable pivoti = -1  // position of pivot
  while stack.Length>0 && si<en do // main recursion loop
    match stack with
      | (s,e)::cdr ->        // :: is "cons", cdr is just a variable here
         si <- s; en <- e    // start and end of partition
         stack <- cdr        // pops stack
      | _ -> raise(Exception("error"))
    i<- si;  pivoti <- -1   // default no pivot
    while i<en-1 && pivoti<0 do  // find position of pivot
      if A.[i]>A.[i+1] then pivoti <- i+1  else  i<-i+1
    if pivoti>=0 then  // if pivot found, partition array via swaps
      k<-si;  
      for i in si..en-1 do  // new variable 'i' created by for loop
        if A.[i]<=A.[pivoti] then 
          let tmp = A.[i] in (A.[i]<-A.[k];  A.[k]<-tmp;  k<-k+1)
      // at this point, k will point to first index of second parition
      stack <- (si,k)::(k,en)::stack // stack "recursive calls"
  // end of main recursion loop
//quicksort

let s = [|"t";"c";"a";"g"|] in 
  sort s;
  printfn "%A" s;;


////  Reference cells (type safe pointers)

let xy = 4;
let px = ref xy;;  // px is assigned as a pointer to 4 (not to address of xy)
px := 5;;         // changes the contents of pointer, px now points to 5
printf "%d\n" !px ;;  //!px dereferences px into the integer value

// references can replace mutable variables.

// Question: what is the difference between  let px = ref 4  and
// let mutable  px = ref 4  ??

// Please note that these pointer operations are NOT the same as those
// found in C.  In C, if you do:
// int x = 2;
// int *p = &x;
// *p = 3;   // x would now be 3,
// but in the F# code above, xy will still be 4: ref xy is the same as ref 4.
// Pointers in F# can replace mutable values, but they cannot make something
// immutable mutable.  3 is always 3, it does not "become 4".
// Pointer operations in C can be used very cleverly, but can also cause
// problems, and I'm not just talking about hacking.

// compile to .exe with fsc misc.fs (fsharpc on Mono)
// run with ./misc.exe   or   mono misc.exe