(*
 * Returns the Cartesian product of elements from xs with
 * elements from ys.
 *
 * @param xs A list of any type.
 * @param ys A list of any type (not necessarily the same as xs!)
 * @return A list of pairs of elements from xs and ys.
 *)
let rec cartesianProduct(xs: 'a list)(ys: 'b list) : ('a * 'b) list =
  match xs,ys with
  | [], _ -> []
  | _ ,[] -> []
  | x::xs',_ ->
    // pair every y from ys with x; call that set zs
    let zs = ys |> List.map (fun y -> (x,y))
    // union (list append) that set with the Cartesian
    // product of xs without x and ys
    zs @ cartesianProduct xs' ys
    
(*
 * Returns the Cartesian product of elements from xs with
 * elements from ys.
 * Zach pointed out after class that the second case above
 * is redundant.  He's right!  Do you see why?
 *
 * @param xs A list of any type.
 * @param ys A list of any type (not necessarily the same as xs!)
 * @return A list of pairs of elements from xs and ys.
 *)
let rec cartesianProduct2(xs: 'a list)(ys: 'b list) : ('a * 'b) list =
  match xs,ys with
  | [], _ -> []
  | x::xs',_ ->
    let zs = ys |> List.map (fun y -> (x,y))
    zs @ cartesianProduct xs' ys
    
(* Call one of these functions like *)
cartesianProduct [1; 2] ["a"; "b"]

(* Note that using an empty list as a parameter runs into ML's 'value restriction'.
 * Value restriction is a rule that says when type inference is allowed to proceed
 * 'safely' (i.e., without error).
 *)
cartesianProduct [] ["a"; "b"]
(*
 * Fails with:
 *  error FS0030: Value restriction. The value 'it' has been inferred to have generic type
    val it : ('_a * string) list    
    Either define 'it' as a simple data term, make it a function with explicit arguments or,
    if you do not intend for it to be generic, add a type annotation.
 * The issue is that F# cannot reason soundly about [] because it does
 * not have a 'concrete type'.  Observe what type [] has in fsharpi:
   > [];;                                                                   
   val it : 'a list
 * which is polymorphic.
 * The fix is to make that list 'concrete' by providing a type.
 *)
let A: string list = []
cartesianProduct A ["a"; "b"]

(* Fun challenge: can you write a Cartesian product function using fold? *)