FA18 CSE 130 midterm practice: solutions to previous midterms.

midterm_practice.ml

(* FA18 CSE 130 Midterm Practice *)

(* FA14 *)
type expr = Const of int | Var of string | Op of string * expr * expr

let rec rename_var e n1 n2 =
  match e with
    | Const c -> Const c
    | Var s -> if s = n1 then Var n2 else Var s
    | Op (a,b,c) -> Op (a, rename_var b n1 n2, rename_var c n1 n2)
;;

let rec to_str e =
  let rec str_helper e top_level =
	  match e with
	    | Const c -> string_of_int c
	    | Var s -> s
	    | Op (a,b,c) ->
        if top_level then (str_helper b false) ^ a ^ (str_helper c false)
        else "(" ^ (to_str b) ^ a ^ (to_str c) ^ ")"
  in str_helper e true
;;

let average_if f l =
  let folding_fn acc next =
    let (s,n) = acc in
    if (f next) then (s+next,n+1) else acc
  in
  let base = (0,0) in
  let res = List.fold_left folding_fn base l in
  let (sum,num) = res in
  if num = 0 then 0 else sum / num
;;

let length_2 l = 
  List.fold_left (+) 0 (List.map List.length l)
;;

let length_3 l =
  List.fold_left (+) 0 (List.map length_2 l)
;;

(* FA13 *)
let count l x =
  let folding_fn acc next = if next = x then acc + 1 else acc in
  List.fold_left folding_fn 0 l
;;

let make_palyndrome l =
  let folding_fn acc next = next::acc in
  List.append (List.fold_left folding_fn [] l) l
;;

let fold_2 f b l =
  let folding_fn acc next =
    let (a,i) = acc in
    (f a next i, i+1)
  in
  let (res,_) = List.fold_left folding_fn (b,0) l in
  res
;;

let rec ith l i d =
  let f acc next index =
    if index = i then next else acc
  in
  fold_2 f d l
;;

type 'a fun_tree =
  | Leaf of ('a -> 'a)
  | Node of ('a fun_tree) * ('a fun_tree)
;;

let rec apply_all t x =
  match t with
    | Leaf l -> l x
    | Node (n1,n2) -> apply_all n2 (apply_all n1 x)
;;

let rec compose t1 t2 =
  match (t1, t2) with
    | (Leaf l1, Leaf l2) -> Node(Leaf l1, Leaf l2)
    | (Node (l1,l2), Node (l3,l4)) -> Node(compose l1 l3, compose l2 l4)
;;

(* SP13 *)
let length l =
  List.fold_left (fun a n -> a + 1) 0 l
;;

let remove l x =
  let folding_fn acc next = 
    if next = x then acc else acc @ [next]
  in
  List.fold_left folding_fn [] l
;;

let rec ith l i d =
  match l with
    | [] -> d
    | h::t -> if i = 0 then h else ith t (i-1) d
;;

let rec update l i n =
  match l with
    | [] -> []
    | h::t -> if i = 0 then n::t else h::(update t (i-1) n)
;;

let rec update2 l i n d =
  match l with
    | [] -> if i > 0 then d::(update2 [] (i-1) n d) else [n]
    | h::t -> if i = 0 then n::t else h::(update2 t (i-1) n d)
;;

let categorize f l =
  let base = [] in
  let fold_fn acc elmt =
    let bin = f elmt in
    update2 acc bin ((ith acc bin []) @ [elmt]) []
  in List.fold_left fold_fn base l
;;

(* WI13 *)
type 'a maybe = None | Some of 'a

let first f l =
  let base = None in
  let fold_fn acc elmt =
    if acc = None && f elmt then Some elmt else acc
  in List.fold_left fold_fn base l
;;

let rec zip l1 l2 =
  match (l1,l2) with
    | ([],[]) -> []
    | (h1::t1,h2::t2) -> (h1,h2)::(zip t1 t2)
    | _ -> []
;;

let map2 f l1 l2 =
  List.map (fun (x,y) -> f x y) (zip l1 l2)
;;

let map3 f l1 l2 l3 =
  List.map (fun (x,(y,z)) -> f x y z) (zip l1 (zip l2 l3))
;;

let rec unzip l =
  match l with
    | [] -> ([],[])
    | (x,y)::t ->
      let tail = unzip t in
      let (a1,a2) = tail in
      (x::a1,y::a2)
;;

(* WI12 *)
let rec split l =
  let llen = length l/2 in
  let base = (llen,[],[]) in
  let fold_fn (i,l1,l2) elmt = 
    if i > 0 then (i-1,l1 @ [elmt],l2) else (i-1,l1,l2 @ [elmt])
  in
  let (_,l1,l2) = List.fold_left fold_fn base l in
  (l1,l2)
;;

let rec merge l1 l2 =
  match (l1,l2) with
    | ([],l) -> l
    | (l,[]) -> l
    | _ ->
      let (h1::t1,h2::t2) = (l1,l2) in
      if h1 <= h2 then h1::(merge t1 l2) else h2::(merge l1 t2)
;;

let rec merge_sort l =
  match l with
    | [] -> []
    | h::t ->
      if t = [] then l
      else
        let (l1,l2) = split l in
        merge (merge_sort l1) (merge_sort l2)
;;

let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) []
;;

let implode l =
  let res = String.create (List.length l) in
  let rec imp i = function
  | [] -> res
  | c :: l -> res.[i] <- c; imp (i + 1) l in
  imp 0 l
;;

let replace s =
  implode (List.map (fun x -> if x = '-' then ' ' else x) (explode s))
;;

let rec app l x =
  match l with
    | [] -> []
    | f::t -> (f x)::(app t x)
;;