*** COMPOSED TYPES ***

Try to predict the type of every expression below, verifying the answers interactively.

("two", true, 2);;
- : string * bool * int = ("two", true, 2)

[("two", true, 2)];;
- : (string * bool * int) list = [("two", true, 2)]

((1,2),(3,4,5));;
- : (int * int) * (int * int * int) = ((1, 2), (3, 4, 5))

[[1;2];[3;4;5]];;
- : int list list = [[1; 2]; [3; 4; 5]]

[[];[];[]];;
- : 'a list list = [[]; []; []]

[1;2;(3,4)];;
     ^^^^^       
Error: This expression has type int * int
       but an expression was expected of type int
Remember this message because it will come back to you quite often when 
you work on your projects. In this example we have inserted a couple int*int 
in the list of int, and this message is made to let you see this mistake.

('a', "tom"::"jerry"::[], 2<3);;
- : char * string list * bool = ('a', ["tom"; "jerry"], true)

###############################################################################

*** VALUE BINDING AND PATTERN MATCHING ***

1) Try to redict the result of the folloving value binding, verifying the answers interactively.

let (a,b) = (5,6);;
val a : int = 5
val b : int = 6

let (c,d) = (2,("xx","yy"));;
val c : int = 2
val d : string * string = ("xx", "yy")

let (e,(f,g)) = (1,(2,3));;
val e : int = 1
val f : int = 2
val g : int = 3

let (l,m,n) = ("xx",(1,2));;
              ^^^^^^^^^^^^
Error: This expression has type string * (int * int)
       but an expression was expected of type 'a * 'b * 'c
This one does not work simply because we are trying to 
assign a couple to a triple.

let o = ("z",(3,4));;
val o : string * (int * int) = ("z", (3, 4)) 

let (p, _ ) = (12, 10);;
val p : int = 12

let (q, 10) = (12, 10);;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
(_, 0)
val q : int = 12
When it's complaining that the matching is not exhaustive, 
we have to check whether we have considered all the possible 
values that we can have on the right-hand side of the equation. 
In this example we are asking that the second element of the 
couple is ALWAYS 10, but OCaml says "look, it can 
be different, for example it can be 0."

let (r, 11) = (12, 10);;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
(_, 0)
Exception: Match_failure ("", 3, 3).
Here is the case when pattern matching breaks because of its 
"non-exhaustiveness".

let u 	= 1::[2;3];;
val u : int list = [1; 2; 3]

let v::w = 1::[2,3];;
Error: This expression has type int * int
       but an expression was expected of type in
Pay attention to the comma (instead of ";")

let v::w = 1::2::3::[];; 
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val v : int = 1
val w : int list = [2; 3]
This match implies that the list cannot be empty and 
OCaml says that the list can be empty, and in that case 
matching would definitely fail. Try this to ensure:
# let v::w = [];;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
Exception: Match_failure ("", 4, 3).

let h::t = [4;5;6];;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val h : int = 4
val t : int list = [5; 6]


2) Try to predict the result of the following expressions, verifying the answers interactively.

let x=4 and y=5+x;;
Error: Unbound value x
During the binding of y, we know that exists a name x, hovewer 
its value is not defined yet. Hence, OCaml says that x doesn't have a value.

let a=1 in let a=2 and b=a in a+b;;
- : int = 3
Here in the parallel binding of a and b, the considered value is 
not 2 (not yet arrived), but the one from the previous binding, hence 1. 
Hence, in the expression "a+b" we have values 2 and 1 for a and b respectfully.

3) Find the pattern for the following expressions that allow to bind the variable x with the value 0.
For example, for an expression (3, true, 0) the following binding is used:
let (_,_,x) = (3,true,0);;

[1;2;33;0;4]
let _::_::_::x::_ = [1;2;33;0;4];; OR
let [_;_;_;x;_] = [1;2;33;0;4];;

[(1,2);(0,1)]
let [_;(x,_)] = [(1,2);(0,1)];;

(("a","b"), (0,"aa",[5;3]))
let (_, (x, _, _))=(("a","b"), (0,"aa",[5;3]));;	

################################################################################
	
*** FUNCTIONS ***

1) Try to predict the type of the following functions, verifying the answers interactively.

fun x -> [x+1;x+2;x+3];;
- : int -> int list = <fun>

fun x -> (x,x,x);;
- : 'a -> 'a * 'a * 'a = <fun>

fun (x,y) -> [x ^ "b"; y];;
- : string * string -> string list = <fun>
OCaml does not know anything about y, however since we are using a list 
where all the elements should be of the same type, and x is definitely a 
string, y is a string as well.

fun (x,y,z) -> (x+(String.length y),z);;
# fun (x,y,z) -> (x+(String.length y),z);;
- : int * string * 'a -> int * 'a = <fun>

2) Define the type of the predefined functions "List.rev", "List.hd" and "List.tl" with the help of the OCaml interpreter.

# List.rev;;
- : 'a list -> 'a list = <fun>
# List.hd;;
- : 'a list -> 'a = <fun>
# List.tl;;
- : 'a list -> 'a list = <fun>


Try to predict the results of the following expressions, verifying the answers interactively.

List.hd [1;2;3];;
- : int = 1

List.hd (List.tl [1;2;3]);;
- : int = 2

List.hd(List.rev [1;2;3]);;
- : int = 3

List.hd(List.tl(List.rev [1;2;3;4]));;
- : int = 3
A reversed list is [4;3;2;1], its tail is [3;2;1], its head is 3.

3) Define the functions "perimeter" and "area" that calculate the perimeter and area of the rectangular triangle given the mesures of the catets.

# let perimeter c1 c2 = c1 +. c2 +. sqrt(c1*.c1 +. c2*.c2);; 
val perimeter : float -> float -> float = <fun>

# let area c1 c2 = c1 *. c2 /. 2.0;;   
val area : float -> float -> float = <fun>


4) Consider the folloing definition of the function.

let rec t = function
     0 -> 0
   | n -> 2 + t(n-1);;

What does this function calculate?	

At every step the funciton decreases n and adds 2 to the result, so it simply
calculates n*2.
val t : int -> int = <fun>

	  
5) Try to evaluate using the interpreter of OCaml the following functions. Then, try it on some input.
Be sure that you understood:
- what the function is doing
- how does the function work

let rec d = function
     0 -> "de"
   | n -> "do"^d(n-1)^"da";;
	
val d : int -> string = <fun>
Puts "do" as a prefix n times, and "da" as a suffix. Then, when n=0, it 
puts "de" in the middle of the string.	

let rec h = function
     0 -> 1
   | n -> h(n-1)+h(n-1);;
   
val h : int -> int = <fun>
Calculates 2^n.

Is it possible to optimize h?

Yes, by calling 2*h(n-1) instead of h(n-1)+h(n-1).

let rec m = function
     (a,0) -> 0
   | (a,b) -> a+m(a,b-1);;

val m : int * int -> int = <fun>
Calculates a*b

let rec f = function
      0 -> true
   |  n -> not(f(n-1));;

val f : int -> bool = <fun>
Calculates whether the given number is even. Returns false otherwise.

let rec g = function
      0 -> []
   |  n -> n::g(n-1);;

val g : int -> int list = <fun>
Returns a list of the n elements (in reversed order)	
	
let rec l = function
     0 -> []
   | n -> n mod 10 :: l(n/10);;
   
val l : int -> int list = <fun>	
Returns a list of the digits of the given number (in reversed order)	

let rec j = function
     0 -> 0
   | n -> n mod 10 + n/10;;
   
val j : int -> int = <fun>   
Returns n mod 10 + n/10
# j 345;;
- : int = 39


6) Define a function "list3" that returns a list that contains doubled values of the three given inputs.
For example, list3 [1;2;3] = [2;4;6]

let list3 [n;m;l] = [n*2;m*2;l*2];;
val list3 : int list -> int list = <fun>

7) Define the following functions using the pattern-matching if possible.

     sumto n         = 1 + 2 + ... + n      
let rec sumto = function
   1 -> 1
 | n -> n + sumto(n-1);;
val sumto : int -> int = <fun>	 
     
     listfrom n      = [n;n-1;...;0]
let rec listfrom = function
      0 -> [0]
   |  n -> n::listfrom(n-1);;
val listfrom : int -> int list = <fun>

     
     strcopy("ab",n) = "ababab..." (n times)
     (using the predefined function "^" for string concatenation)
let rec strcopy = function
   (s,0) -> ""
 | (s,n) -> s ^ strcopy(s,n-1);;
val strcopy : string * int -> string = <fun>	 
     
     power(x,n)      = x**n
let rec power = function
   (x,0) -> 1
 | (x,n) -> x*power(x,n-1);;
val power : int * int -> int = <fun>
     
     listcopy(a,n)   = [a;a;...;a] (n times)
let rec listcopy = function
   (s,0) -> []
 | (s,n) -> s::listcopy(s,n-1);;
val listcopy : 'a * int -> 'a list = <fun>
     
     sumEvens n     = 0 + 2 + ... + n (n is even)
exception Odd;;
let rec sumEvens = function
   0 -> 0
 | n -> if n mod 2 = 0 then n + sumEvens(n-2)
                       else raise Odd;;
val sumEvens : int -> int = <fun>	 
     
     listOdds n     = [n; n-2; ...; 1] (n is odd)
exception Even;;
let rec listOdds = function
   1 -> [1]
 | n -> if n mod 2 <> 0 then n::listOdds(n-2)
                       else raise Even;;
val listOdds : int -> int list = <fun>
     
     nat(n)          = "succ(...(succ(zero)))" (concatenate n times "succ")
let rec nat = function
   0 -> "zero"
 | n -> "succ(" ^ nat(n-1) ^ ")";;
val nat : int -> string = <fun>
     
     listTo(n)       = [1;..;n]
let listTo n =
   let rec aux = function
      0 -> []
    | 1 -> [1]
    | n -> n::aux(n-1)
   in List.rev(aux n);;
val listTo : int -> int list = <fun>