(* Programming Languages (F28PL) lecture transcript - 27th September at 15:15 *)
(* Solving exercises on course website *)
(* Question B *)

(* Question B1 *)
(* Find the integer logarithm to the base 2 of an integer n by repeatedly dividing by 2
log2 1 = 0
log2 n = 1+log2 (n div 2)
*)
fun log2 1 = 0 
  | log2 n = 1 + log2 (n div 2);

(* Tests *)
log2 1; (* should return 0 *)
log2 8; (* should return 3 *)
log2 1555 (* should return 10 *)

(* Question B2 *)
(* Find the square root of an integer x by repeatedly decrementing an initial guess s:
sqrt x s = s if s*s <= x
sqrt x s = sqrt x (s-1) if s*s > x 
*)
fun sqrt x s = if s*s <= x then s else sqrt x (s-1);

(* Tests *)
(* tests go here *)

(* Question C1 *)
(* Write a function to drop the first n elements of a list l:
drop n l : int -> 'a list -> 'a list  
drop 3 [1,2,3,4,5] ==> [4,5]
    To drop 0 elements from a list return the list.
    To drop n elements from the empty list, return the empty list.
    To drop n elements from a list, drop n-1 elements from the tail.
*)
fun drop 0 l = l 
  | drop n [] = []
  | drop n (h::t) = drop (n-1) t;

fun double [] = []
  | double (h::t) = hh:hh:(double t);

(* Patter matching *)
fun twozeroes (0,0) = true 
  | twozeroes _ = false;

fun twozeroes (x,y) = if x = 0 andalso y = 0 then true else false; (* A vulgar version *)
fun twozeroes (x,y) = x=0 andalso y=0; (* Shorter way to write it *)

fun twozeroes (z:int*int) = (#1 z)=0 andalso (#2 z)=0;

(* Transcript of the interactive PolyML shell *)
Char.>= (#"0",#"5"); (* returns false *)
ord #"0"; (* ASCII code of '0' is 48 *)
ord #"5"; (* ASCII code of '5' is 53 *)

Char.>= (#"a", #"A"); (* Lowercase a is bigger than uppercase A in ASCII *)
ord #"a";
ord #"A";

#"a" >= #"A"; (* Same as Char.>= (more ad-hoc polymorphism) *)

(* Cons operator which has type 'a * 'a list -> 'a list *)
op ::;

(* Head function has type 'a list -> 'a *)
hd;

(* Decoding "IBM" *)
Char.succ;
Char.succ #"H";
map; (* has type ('a -> 'b) -> 'a list -> 'b list *)
val succString = implode o (map Char.succ) o explode;
succString "HAL"; (* returns "IBM" *)