(*cproduct*)
  
(* Compute the Cartesian product of sets
   The product of n sets S1*S2*..*Sn is the set of all n-tuples 
   <E1,E2,..,En> where E1 is a member of S1, E2 is a member of S2, ...
   and En is a member of Sn. For example, the Cartesian product of
   [[1,2],[3,4,5],[6,7]] = [[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],
                            [2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]] *)

(* Note that although lists are used here, they should be considered as sets *)

fun join x e = x@[e];
(* Given a list (set) x and an element e, append e to that list (set) *)

join [1,2] 3;

fun vp [] y = []
   |vp (e::x) y = map (join e) y @ vp x y;
(* Vector product? Given a set of sets x and a set y deliver the set 
   of sets z, such that: each ste of z is a set of x joined with an
   element of y *)

vp [[1,2],[3,4]] [100,200,300]

fun cartesian_product [] = []
   |cartesian_product (ex::x) =
    let fun cp y [] = y
           |cp y (ez::z) = cp (vp y ez) z
    in cp (map (fn e => [e]) ex) x end;
(* Given a set of sets, produce the Cartesian product.
   The "inner" function cp takes as arguments a set of sets y
   and a set of sets z. *)

cartesian_product [[1,2,3]];
cartesian_product [[1,2,3],[4,5],[6,7,8],[9],[10,11]];

(* Exercise:
   The function "cartesian_product" has a significant application
   with respect to predicate calculus. For example, assume we
   have the expression ((A B) (C D) (K)) -> Z. This may be interpreted
   as ((A and B) or (C and D) or (K)) implies Z. It may be represented 
   as follows: *)

val Z = [["A","B"],["C","D"],["K"]];

(* Assume we also have *)

val Y = [["J","K","L"],["L","E"]];
val X = [["J"]];

(* Also assume that (X Y Z) -> X2, that is (X and Y and Z) implies X2.
   Express X2 in terms of "A","B","C","D","E","J","K","L".

   If we have an expression (A B A) reduce this to (A B).
   If we have a disjunction of conjunction ((A B C) (B C) (C)) reduce to ((C)).

   Note that lists must be "flattened", that is conjunctions produced
   must be appended.

   If you can do this, what do you think have created? *)

val X2 = [X,Y,Z];

(* Lets use dfs, and assume again that we have an ongoing process where
   we have a tuple (r,d), where r is the result we are constructing, and
   d is the data that we can use to construct r.

   Assume in example above that initially r=[] and d = [[1,2],[3,4,5],[6,7]]
   The successors of ([],[[1,2],[3,4,5],[6,7]]) would then be the list of tuples
   [([1],[[3,4,5],[6,7]]),([2],[[3,4,5],[6,7]])]. The successors of the tuple
    ([1],[[3,4,5],[6,7]]) would then be the list of tuples
   [([1,3],[[6,7]]),([1,4],[[6,7]]),([1,5],[[6,7]])]

  This then looks very similar to the technique we used for perm *)

fun succ_cprod (r,(h::t)) = map (fn e => (r@[e],t)) h;

fun test_cprod (_,d) = null d;

fun result_cprod (r,_) = r;

fun dfs_cprod = dfs