(* ANOTHER COMMON SIDE-EFFECT GENERATING FUNCTION *)

#open "printf";;
(* # means that this is a directive - in this case, the directive is
   opening one of the modules in the standard library *)

print "hello world\n";;
print (string_of_int(3+8));;
print (string_of_int(3+8)^"\n");;
print (string_of_float(1.0E50));;
print (string_of_bool(true));;

(* There is no string_of_list.  Instead, for int lists: *)

let null list = if (list=[]) then true else false;;
let rec printList(l) = if null(l)
                       then ()
		       else ( print(string_of_int(hd l)^"\n");
			      printList(tl l)
			    );;
printList [1;2;3;4];;

(*
The else-expression is a *statement sequence*.  Statement sequences
evaluate to the value of the last statement in the sequence.  Here,
that's always ().  Because the value of every statement other than
the last will be discarded, statement sequences are generally only
good for generating side effects of some kind.

or (better): *)

let printList = map(function x -> print(string_of_int(x)^"\n"));;
printList [1;2;3;4];;

(* or *)

let printList = do_list(function x -> print(string_of_int(x)^"\n"));;
printList [1;2;3;4];;

(*
do_list is sort of like map, but it throws the list of results away,
returning the unit () instead. do_list only applies to functions that
return unit, so the result is never that interesting anyway. 

or given: *)
let conc(x)(y) = x^y;;
let rec reduce = function (f,[],z) -> z
                        | (f,(x::xs),z) -> f(x)(reduce(f,xs,z));;
(* actually, this is built into CaML under the name list_it - there is
   also an it_list that iterates into the first argument *).

let printList(l) = print(reduce((function x -> conc(string_of_int(x)^"\n")),l,""));;
printList [1;2;3;4];;

(* Notice the difference with respect to: *)

let printList(l) = print(reduce((function x -> conc(string_of_int(x))),l,"\n"));;
printList [1;2;3;4];;

(*
SEQUENTIAL COMPOSITION: certain operations (notably those with side-effects)
  are very sensitive to the order in which their component parts are evaluated
For these, you use STATEMENT LISTS in CaML: *)
(print("hello ");print("world "));;

(*
In general, when ML evaluates (E1 ; E2 ; ... ; En);;, it evaluates E1 first,
 then E2, then .... En.
The value/type of the statement list is the value/type of the last expression: *)
(print("hello ");print("world ");"done");
"I am "^(print("hello ");print("world ");"done");;
(*
You should avoid writing code that generates such warnings - it means that you
are throwing results away, which is generally an indication that you're using
code in a manner other than how it was written.

Statement lists can also be used in recursions: *)
let rec myprint l = if null(l) then 0
	   	    else (print(string_of_int(hd l)); 
		          print "\n"; 
		          (hd l) + myprint (tl l));;
myprint [1;2;3;4;5];;

(*
LOCAL VARIABLES
*)

let print_powers(x) =
  let
      square = x*x and
      cube = x*x*x
  in
     ( print(string_of_int(x)^"\n");
       print(string_of_int(square)^"\n");
       print(string_of_int(cube)^"\n")
     );;

(* better: *)

let print_powers2(x) =
  let square = x*x
    in
      let cube = square*x  (* have to use a second let to use square on RHS *)
      in ( print(string_of_int(x)^"\n");
           print(string_of_int(square)^"\n");
           print(string_of_int(cube)^"\n")
         );;

(* but not: *)
let print_powers2(x) =
  let
      square = x*x and
      cube = square*x
  in
     ( print(string_of_int(x)^"\n");
       print(string_of_int(square)^"\n");
       print(string_of_int(cube)^"\n")
     );;

(* You can bind functions to local variables using function/->, too.

POOR-MAN'S OBJECT ORIENTATION USING REFERENCES, FUNCTIONS AND LET *)

let stack = 
  let
      s = ref []
  in
      (function ("push",arg) -> (s := (arg::(!s)); arg)
	      | ("pop",arg) -> let t = (hd (!s))
                                in (s := (tl (!s)) ; t)
 	      | ("empty?",arg) -> if null(!s) then 1 else 0
      );;

stack ("push",3);;
stack ("push",2);;
stack ("push",1);;
stack ("empty?",0);;
stack ("pop",0);;
stack ("pop",0);;
stack ("pop",0);;
stack ("empty?",0);;
stack ("pop",0);;

(*
This is still a bit of a mess:
  1) 1/0 used for true/false in the result of "empty?",
  2) "pop" and "empty" have to be called with a dummy argument,
  3) "push" receives the pushed value back - prob. should be ().
and we can clean this up once we learn a bit more CaML.  For now, however,
notice that the outer let is being used to *hide* the details of
our internal representation of the stack (a list reference) - nobody can see
s except stack.  And notice that the inner let is being used to
preserve the top of the stack before we destroy it by popping the stack.
These are both very common applications of local variables.
  Also observe how an anonymous function is being used to receive
messages passed to stack.  Stack is always a function, no matter how
many times we call it.  So it can continue to receive messages even
as the internal representation, s, changes.

Another reason to use local variables is to avoid computing something
more than once, particularly if it takes a long time to do so:

let f(x) =
  let bmf = big_monster_function(x)
  in g(bmf+bmf,bmf/bmf);;
  
RECURSION
A recursive function is a function that calls itself: *)

let rec factorial(n) = if n=0                  (* test *)
                       then 1                  (* base case *)
		       else n*factorial(n-1);; (* recursive case *)
(* notice the need for rec - this is required for recursive functions *)
factorial(4);;

(*  A sample *trace*:
e
factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)
4 * 3 * 2 * 1 * 1
4 * 3 * 2 * 1
4 * 3 * 2
4 * 6
24

Base case may not be for n=0... *)
let rec last(l) = if null(tl l)
                  then (hd l)
                  else (last(tl l));;
last [1;2;3;4];;

(*
This is called *cdr-recursion*.

There is also *car-recursion* (recursion on (hd l)), but those are
  more difficult to come by in CaML.

What if no test?  Then no termination in the worst case, possibly
  an exception raised.
Recursive function may not terminate with a poorly chosen test
  either, e.g.: *)

let rec sloppy_add(x,n) = if n=0
	   	          then x
		          else 2 + sloppy_add(x,n-2);;
sloppy_add(4,2);;
(* don't try this at home:
sloppy_add(4,3);;
*)

(*
SPECIAL KINDS OF RECURSION

(A)
Tail-recursion: 1) there is at most one recursive call made in any
                   execution of function body
                2) the recursive call is in the "last" function application in
                   function body
Tail-recursion is implemented very efficiently and should be used whenever
possible. *)

let rec member(x,l) = if null(l)
		      then false
	              else if (x=hd(l))
		           then true
		           else member(x,tl(l));;
member(3,[1;2;3]);;
member(4,[1;2;3]);;

(* has the trace:
member(4,[1;2;3]);;
member(3,[1;2;3]);;
member(3,[2;3]);;
member(3,[3]);;
*)

(*
A good compiler will handle built-ins like :: specially, so 
these often count as tail-recursive, too: *)

let rec append(l,m) = if null(l)
		      then m
		      else (hd l)::append((tl l),m);;

(* trace:
append([1,2,3],[4,5,6])
1::append([2,3],[4,5,6])
1::2::append([3],[4,5,6])
1::2::3::append([],[4,5,6])
1::2::3::[4,5,6]
[1,2,3,4,5,6]
*)

(* Unfortunately, CaML compilers generally don't.  This version
of append is not tail-recursive in CaML.  We'll cover a general
method for tweaking these into a tail-recursion later.

If recursion is not tailed, then there is an unwinding phase: *)

let rec factorial(n) = if n=0                  (* test *)
                       then 1                  (* base case *)
		       else n*factorial(n-1);; (* recursive case *)
factorial(4);;

(* trace:
factorial(4)                             ----
4 * factorial(3)                          |
4 * 3 * factorial(2)                     WIND
4 * 3 * 2 * factorial(1)                  |
4 * 3 * 2 * 1 * factorial(0)             ----
4 * 3 * 2 * 1 * 1                         |
4 * 3 * 2 * 1                            UNWIND
4 * 3 * 2                                 |
4 * 6                                    ----
24
*)

(* But be careful... *)
let rec evenlen(l) = if null(l)
		     then true
		     else not(evenlen(tl l));;

(* trace:
evenlen [1,2,3,4]
not(evenlen [2,3,4])
not(not(evenlen [3,4]))
not(not(not(evenlen [4])))
not(not(not(not(evenlen []))))
not(not(not(not(true))))
not(not(not(false)))
not(not(true))
not(false)
true

(B)
Linear recursion: 1) there is at most one recursive call made in any 
                   execution of function body

factorial and evenlen are linear-recursive, but not tail-recursive

This is not even linear-recursive: *)
let rec fib(n) = if (n=0) then 0
	         else if (n=1) then 1
	         else fib(n-1) + fib(n-2);;

(*
Non-linear-recursive functions have more complicated traces than
just a single wind and unwind.  Sometimes we look at them as trees:

            fib(4)
           /      \
     fib(3)        fib(2)
     /     \       /     \
fib(2)    fib(1) fib(1)  fib(0)
|     \     |      |       |
|      \    1      1       1
fib(1) fib(0)
  |      |
  1      1

(C)
Flat recursion: recursion applied over 'top' items of a list *)
append ([[1;2;3];[4;5;6]],[[7;8;9];[0;1;2]]);;

(* 
There's even a built-in flat_map : ('a -> 'b list) -> 'a list -> 'b list.

vs.
Deep recursion (aka tree recursion): recursion applied arbitrarily deeply
We'll see examples of this later, once we learn how to build structured
datatypes like trees.

(D)
Mutual recursion: two functions that call each other rather than themselves

let evenlen(l) = if null(l)
		 then true
		 else oddlen(tl l);;
let oddlen(l) = if null(l)
		then false
		else evenlen(tl l);;

(* Can't do it!  Instead, we must define them mutually using *and*: *)

let rec
    evenlen(l) = if null(l)
		 then true
		 else oddlen(tl l)
    and 
    oddlen(l) = if null(l)
		then false
		else evenlen(tl l);;

(* Notice the slight change in base case, as well as the absence of ';' in evenlen. *)