(* Signature for warmup problems.  Should be implemented in the
 * structure Warmup : WARMUP, found in warmup.sml.
 *)
signature WARMUP =
sig
  (* compound rator n x
   *
   * compounds a binary operator _rator_ so that:
   *   compound (op f) 0 x = x
   *   compound (op f) 1 x = x f x
   *   compound (op f) 2 x = x f (x f x)
   *   compound (op f) n x = x f (x f ... (x f x)...)
   *     where f is applied exactly n times
   *)
  val compound : ('a * 'a -> 'a) -> int -> 'a -> 'a

  (* acompound rator n x
   *
   * If _rator_ is associative, it's not necessary to apply it n times
   * to get the right result.  acompound should produce the same result
   * as compound for associative operators, but should apply the
   * operator only O(log n) times rather than n times.
   *)
  val acompound : ('a * 'a -> 'a) -> int -> 'a -> 'a

  (* pow base exp
   *
   * Computes base^exp using acompound for integer exponentiation.
   *)
  val pow : int -> int -> int

  (* fib n
   *
   * Computes the nth Fibnacci number, where fib 0 = fib 1 = 1.
   *
   * Your definition of fib should *not* use if-then-else.
   *)
  val fib : int -> int

  (* isVowel clst
   *
   * A predicate that returns true if the first element of the list is a
   * vowel, or false if not a vowel or if the list is empty.
   *
   * This function should not use if-then-else, and should use the
   * wildcard match _ wherever possible.
   *)
  val isVowel : char list -> bool

  (* myNull lst
   *
   * Tells whether a list is empty or not.  Must run in constant time,
   * and must not use the Standard Basis function null nor if-then-else.
   *)
  val myNull : 'a list -> bool

  (*
   * myFoldr f x lst
   *
   * Like foldr in the Standard Basis, myFoldr accumulates a list from
   * right to left, using the function f, and with x as the starting value.
   * For example,
   *
   *    myFoldr f x [a, b, c, d] = f (a, f (b, f (c, f (d, x))))
   *
   * Write myFoldr using recursion, but without if-then-else.
   *)
  val myFoldr : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

  (*
   * myFoldl f x lst
   *
   * Like foldl in the Standard Basis, myFoldl accumulates a list from
   * left to right using the function f, and with x as the starting value.
   * For example,
   *
   *    myFoldl f x [a, b, c, d] = f (d, f (c, f (b, f (a, x))))
   *
   * Write myFoldl using recursion, but without if-then-else.
   *)
  val myFoldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

  (* zip l1 l2
   *
   * Given two lists of equal lengths, returns the equivalent list of
   * pairs, e.g.:
   *
   *   - zip ([1, 2, 3], [#"c", #"b", #"a"]);
   *   val it = [(1, #"c"), (2, #"b"), (3, #"a")] : (int * char) list
   *
   * If the lists are not of equal length, zip should raise an
   * exception.  zip should of course _not_ use if-then-else, and should
   * run in linear time.
   *)
  val zip : 'a list * 'b list -> ('a * 'b) list

  (* unzip lst
   *
   * Computes the inverse of zip.  For example:
   *
   *   - unzip [(1, true), (2, false)];
   *   val it = ([1, 2], [true, false]) : int list * bool list
   *)
  val unzip : ('a * 'b) list -> 'a list * 'b list

end