(* Assignment 1 *) (* Do not edit this line. *)
(* Student name: Andi Rayhan Chibrandy, Id Number: 260567400 *) (* Edit this line. *)

(* In the template below we have written the names of the functions that
you need to define.  You MUST use these names.  If you introduce auxiliary
functions you can name them as you like except that your names should not
clash with any of the names we are using.  We have also shown the types
that you should have.  Your code must compile and must not go into infinite
loops.  *)


let rec slhelper (l:float list) acc:float =
  match l with
  | [] -> acc
  | x::rest -> slhelper rest (x+acc)

let rec sqlisthelper (l:float list) (acc:float list)=
  match l with
  | [] -> acc
  | x::rest -> sqlisthelper rest (acc@[(x*x)])

let rec listlength (l:float list) (acc:float) =
  match l with
  | [] -> acc
  | x::rest -> listlength rest (acc+1.0)

let rec mdhelper (l:float list) (mean:float) (acc:float list) =
  match l with
  | [] -> acc
  | x::xs -> mdhelper xs mean (acc@[(x-mean)])




(* Question 1 *) (* Do not edit this line. *)

(* val sumlist : l:float list -> float *)
let rec sumlist l = slhelper l 0.0(* remove failwith and replace with your code *)

(* val squarelist : l:float list -> float list *)
let rec squarelist l = (* remove failwith and replace with your code *)
  sqlisthelper l []

(* val mean : l:float list -> float *)
let mean l = (sumlist l)/(listlength l 0.0)(* remove failwith and replace with your code *)

(* val mean_diffs : l:float list -> float list *)
let mean_diffs l = mdhelper l (mean l) [](* remove failwith and replace with your code *)

(* val variance : l:float list -> float *)
let variance l = (* remove failwith and replace with your code *)
  (sumlist (squarelist (mean_diffs l)))/(listlength l 0.0)

(* End of question 1 *) (* Do not edit this line. *)

(* Question 2 *) (* Do not edit this line. *)

(* val memberof : 'a * 'a list -> bool when 'a : equality *)
let rec memberof l = (* remove failwith and replace with your code *)
  let rec loop (l, list) =
    match list with
    | [] -> false
    | x::xs ->
      if x = l then true
      else loop(l, xs)
  match l with
  | (elem, list) -> loop (elem, list)


(* val remove : 'a * 'a list -> 'a list when 'a : equality *)
let rec remove l = (* remove failwith and replace with your code *)
  let rec loop elem list dummy =
    match list with
    | [] -> dummy
    | x::xs ->
      if x = elem then loop elem xs dummy
      else loop elem xs (dummy@[x])
  match l with
  | (elem, l1) -> loop elem l1 []

(* End of question 2 *) (* Do not edit this line *)

(* Question 3 *) (* Do not edit this line *)

(* val isolate : l:'a list -> 'a list when 'a : equality *)
let rec isolate l = (* remove failwith and replace with your code *)
  let rec loop l1 dummy =
    match l1 with
    | [] -> dummy
    | x::xs ->
      if (memberof(x, dummy)) then loop xs dummy
      else loop xs (dummy@[x])
  loop l []

(* End of question 3 *) (* Do not edit this line *)

(* Question 4 *) (* Do not edit this line *)

(* val common : 'a list * 'a list -> 'a list when 'a : equality *)
let rec common l = (* remove failwith and replace with your code *)
  let rec loop la lb dummy =
    match la with
    | [] -> dummy
    | x::rest ->
      if memberof(x, lb) && not (memberof(x, dummy))
      then loop rest lb (dummy@[x])
      else loop rest lb dummy
  match l with
  | (l1, l2) -> loop l1 l2 []


(* End of question 4 *) (* Do not edit this line *)

(* Question 5 *) (* Do not edit this line *)

(* val split : l:'a list -> 'a list * 'a list *)
let rec split l = (* remove failwith and replace with your code *)
  let rec loop l1 (l2,l3) =
    match l1 with
    | [] -> (l2,l3)
    | x::rest -> loop rest (l3@[x], l2)
  loop l ([],[])

(* val merge : 'a list * 'a list -> 'a list when 'a : comparison *)
let rec merge l = (* remove failwith and replace with your code *)
  let rec loop (l1,l2) =
    match (l1,l2) with
    | (xs,[]) | ([],xs) -> xs
    | (x::tx, y::ty) ->
      if x < y then x::loop(tx, l2)
      else y::loop(l1, ty)
  match l with
  | (l1, l2) -> loop(l1, l2)

(* val mergesort : l:'a list -> 'a list when 'a : comparison *)
let rec mergesort l = (* remove failwith and replace with your code *)
  match l with
  | [] -> []
  | [x] -> [x]
  | _ ->
    let (l1,l2) = split l in
    merge ((mergesort l1),(mergesort l2))

(* End of question 5 *) (* Do not edit this line *)