module type Stack = sig
  type 'a t

  val empty : 'a t

  val isEmpty : 'a t -> bool

  val head : 'a t -> 'a

  val tail : 'a t -> 'a t

  val cons : 'a -> 'a t -> 'a t

  val join : 'a t -> 'a t -> 'a t

  val suffixes : 'a t -> 'a t t

  val update : int -> 'a -> 'a t -> 'a t

  val get : int -> 'a t -> 'a
end

module Mylist : Stack = struct
  type 'a t = 'a list

  let empty = []

  let isEmpty = function | [] -> true | _ -> false

  let head xs = List.hd xs

  let tail xs = List.tl xs

  let cons x xs = x :: xs

  let rec join xs ys = match xs with
    | [] -> ys
    | x :: xs1 -> x :: (join xs1 ys)

  let rec suffixes xs = match xs with
    | [] -> [[]]
    | _ :: xs1 as xs -> xs :: (suffixes xs1)

  let update idx v xs =
    let rec aux idx v xs = match idx, xs with
      | _, [] -> failwith "Empty"
      | 0, _ :: xs1 -> v :: xs1
      | idx, x :: xs1 -> x :: (aux (idx - 1) v xs1)
    in
    if idx < 0 then failwith "Invalid index"
    else aux idx v xs

  let get idx xs =
    let rec aux idx xs = match idx, xs with
      | _, [] -> failwith "Empty"
      | 0, x :: _ -> x
      | idx, _ :: xs1 -> aux (idx - 1) xs1
    in
    if idx < 0 then failwith "Invalid index"
    else aux idx xs
end

(* Test using a functor *)
module StackTest (S : Stack) = struct
  let cs = S.empty in
  let cs1 = S.cons 1 cs in
  let cs2 = S.cons 2 cs1 in
  assert (S.get 0 cs1 = 1) ;
  assert (S.get 0 cs2 = 2) ;
  assert (S.get 1 cs2 = 1)
end

(* Test using a first class module *)
let test_stack (stack : (module Stack)) =
  let module S = (val stack) in
  let cs = S.empty in
  let cs1 = S.cons 1 cs in
  let cs2 = S.cons 2 cs1 in
  assert (S.get 0 cs1 = 1);
  assert (S.get 0 cs2 = 2);
  assert (S.get 1 cs2 = 1)

(* The tests will run on module construction (when the functor is instantiated) *)
module X = StackTest(Mylist)

let () = test_stack (module Mylist)

(*
(module M) is the syntax for passing a module argument
(val M) is for unpacking the module value
*)