(* Question 1 *)

let rec find_map (f : ‘a -> ‘b option) (l : ‘a list) : ‘b option =
match l with
| [] -> None
| hd :: lss ->
match f hd with
| None -> find_map f lss
| Some v -> Some v
;;

let partition (p : ‘a -> bool) (l : ‘a list) : (‘a list * ‘a list) =
let splitter (yes, no) e = if p e then (e::yes, no) else (yes, e::no) in
let yess, noo = List.fold_left splitter ([], []) l in
(List.rev yess, List.rev noo)
;;

.

(* Question 2 *)

exception WrongPassword
exception AccountLocked

type password = string
type address = string
type masterpass = password

type pass_manager = {
save : masterpass -> address -> password -> unit;
get_force : masterpass -> address -> password option;
get : masterpass -> address -> password option;
update_master : masterpass -> masterpass -> unit;
count_ops : masterpass -> int;
} ;;

let encrypt masterpass pw = masterpass ^ “,” ^ pw
let decrypt masterpass pw = List.hd (List.tl (String.split_on_char ‘,’ pw))

let make_manager (masterpass : masterpass) : pass_manager =
let ref_mp : masterpass ref = ref masterpass in
let ref_wrong_pw : int ref = ref 0 in
let ref_successful_call : int ref = ref 0 in
let ref_list : (address * password) list ref = ref [] in

(* Helper functions *)

let check_mp (mp : masterpass) = mp = !ref_mp in
let is_not_locked = (!ref_wrong_pw) <> 3 in
let report_wrong_call () = ref_wrong_pw := !ref_wrong_pw + 1 in

(* Manager functions *)
let save’ (mp : masterpass) addr pw : unit =
if is_not_locked then
if check_mp mp then
ref_list := (addr, pw)::!ref_list
else begin
report_wrong_call ();
raise WrongPassword
end
else
raise AccountLocked
in

let get_force’ mp addr =
find_map (fun (adr, pw) ->
if adr = addr then Some (decrypt mp pw)
else None) ref_list.contents
in

let get’ mp addr =
if is_not_locked then
if check_mp mp
then
get_force’ mp addr
else begin
report_wrong_call ();
raise WrongPassword
end
else
raise AccountLocked
in

let update_master’ old_mp new_mp : unit =
if is_not_locked then
if check_mp old_mp
then
let _ = List.map
(fun (addr, lp) ->
(addr, encrypt new_mp (decrypt old_mp lp))
) ref_list.contents
in ref_mp := new_mp
else begin
report_wrong_call ();
raise WrongPassword
end
else
raise AccountLocked
in

let count_ops’ mp : int =
if is_not_locked then
if check_mp mp
then begin
ref_successful_call := !ref_successful_call + 1;
!ref_successful_call
end
else begin
report_wrong_call ();
raise WrongPassword
end
else
raise AccountLocked
in
(* Brand-new record *)
let account = {
save = save’;
get_force = get_force’;
get = get’;
update_master = update_master’;
count_ops = count_ops’;
} in account
;;

(* Question 3 *)

let rec catalan n =
if n = 0 then 1
else
let rec aux i n acc =
if i > n then acc
else aux (i + 1) n (acc + catalan i * catalan (n – i))
in
aux 0 (n-1) 0
;;

(* Counting values at same time *)
let catalan_count (n : int) : (int * int) =
let count_rec_calls : int ref = ref 0 in
let rec inner_catalan nn =
if nn = 0 then
begin
incr count_rec_calls;
1
end
else
let rec aux i ni acc =
if i > ni then acc
else
aux (i + 1) ni (acc + inner_catalan i * inner_catalan (ni – i))
in
begin
incr count_rec_calls;
aux 0 (nn-1) 0
end
in inner_catalan n, !count_rec_calls
;;

type stats = {
entries : int ref;
lkp : int ref
} ;;

(* Memoization function *)
let memoize (f : (‘a -> ‘b) -> ‘a -> ‘b) (stats : stats) : ‘a -> ‘b =
let hash = Hashtbl.create 1000 in
let rec f’ x =
match Hashtbl.find_opt hash x with
| Some b -> stats.lkp := !(stats.lkp) + 1; b
| None ->
let value = f f’ x in
begin
Hashtbl.add hash x value;
stats.entries := !(stats.entries) + 1;
value
end
in f’
;;

(* Version of catalan that can be memoized *)
let memo_cat (recf : int -> int) (n : int) : int =
if n = 0 then 1
else
let rec aux i n acc =
if i > n then acc
else aux (i + 1) n (acc + recf i * recf (n – i))
in aux 0 (n-1) 0
;;

let catalan_m (n : int) : int * stats =
let state = { entries = ref 0; lkp = ref 0} in
((memoize memo_cat state) n , state)
;;