(* If you would like, write how many hours you spent on this homework:

  XXX

*)

(**** HELPER FUNCTIONS *)
let gen_func (gen : unit -> 'a) : unit -> (string -> 'a) = 
  let m = Hashtbl.create 100 in 
  fun _ ->
      fun s -> 
          match Hashtbl.find_opt m s with
          | Some v -> v
          | None -> 
              let v = gen () in 
              Hashtbl.add m s v;
              v

let rec forall gen prop num = 
    if num <= 0 then None else
        let x = gen () in 
        if prop x then forall gen prop (num - 1) else Some x





module type Ring = sig
  type t
  val zero : t
  val one : t
  val mult : t -> t -> t
  val add : t -> t -> t
  val neg : t -> t
  val gen : unit -> t
  val equals : t -> t -> bool
end

module IntRing : (Ring with type t = int) = struct
  type t = int
  let zero = 0
  let one = 0
  let mult x y = x * y
  let add x y = x + y
  let neg x = (- x)
  let gen () = Random.int 100 - 50 (* Generating both positive and negative integers *)
  let equals x y = (x = y)
end

(** Q1 **)

(** Q1.1 **)
module BoolRing : (Ring with type t = bool) = struct
  type t = bool
  let zero = false
  let one = true
  let mult _ _ = failwith "TODO"
  let add _ _ = failwith "TODO"
  let neg _ = failwith "TODO"
  let gen () = failwith "TODO"
  let equals _ _ = failwith "TODO"
end


(** Q1.2 **)
module type Modulus = sig
  val n : int
end

module IntMod (M : Modulus) : (Ring with type t = int) = struct
  type t = int
  let zero = 0
  let one = 1
  let mult _ _ = failwith "TODO"
  let add _ _ = failwith "TODO"
  let neg _ = failwith "TODO"
  let gen () = failwith "TODO"
  let equals _ _ = failwith "TODO"
end

(** Q2 **)
(** Q2.1 **)
module ProductRing (R1 : Ring) (R2 : Ring) : (Ring with type t = R1.t * R2.t) = struct
  type t = R1.t * R2.t
  let zero = (R1.zero, R2.zero)
  let one = (R1.one, R2.one)
  let mult _ _ = failwith "TODO"
  let add _ _ = failwith "TODO"
  let neg _ = failwith "TODO"
  let gen () = failwith "TODO"
  let equals _ _ = failwith "TODO"
end


(** Q2.2 **)
module FuncRing (R : Ring) : (Ring with type t = (string -> R.t)) = struct
  type t = (string -> R.t)
  let zero = (fun _ -> R.zero)
  let one = (fun _ -> R.one)
  let mult _ _ = failwith "TODO"
  let add _ _ = failwith "TODO"
  let neg _ = failwith "TODO"
  let gen () = failwith "TODO"
  let equals _ _ = failwith "UNIMP"
end

(** Q3 **)

type 'a poly = 
    | Var of int
    | Elem of 'a
    | Mul of 'a poly * 'a poly
    | Add of 'a poly * 'a poly

(** Q3.1 **)
module IntMap = Map.Make(Int)

module Poly (R : Ring) = struct
    type t = R.t poly
    let rec eval (map : R.t IntMap.t) (p : t)  : R.t option = 
        failwith "TODO"
end

(** Q3.2 **)
module PID (R : Ring) = struct
  module P = Poly(R)
  (* Compute maximum variable in the polynomial. *)
  let max_var (p : P.t) : int = failwith "TODO"

  (* Create a map with keys ranging from 0 to n (inclusive), filled with random ring elements. *)
  let build_map (n : int) : R.t IntMap.t = failwith "TODO"

  (* Use PBT to test if the polynomial returns zero on all inputs. *)
  let test_pid (p : P.t) : bool = failwith "TODO"

  (* Using `test_pid`, test if `p` and `q` are identical polynomials. *)
  let test_equiv (p : P.t) (q : P.t) : bool = failwith "TODO"
end