(*dfs*)
(* Applying "depth first search" to generate a
permutation of a sequence S *)

fun dfs [] test succ result = []
   |dfs (n::q) test succ result =
        if test n
        then (result n)::(dfs q test succ result)
        else dfs ((succ n)@q) test succ result;

(* dfs takes as arguments:
   a list of nodes that have been visited
   predicate to test if node is a leaf
   function to generate successors 
   function to interpret leaf as a result *)

fun bfs [] test succ result = []
   |bfs (n::q) test succ result =
        if test n
        then (result n)::(bfs q test succ result)
        else bfs (q@(succ n)) test succ result;

(* Note difference between dfs and bfs *)

(* Produce the permutation of a set/list. For example
   perm [1,2,3] = [[1,2,3],[1,3,2],
                   [2,1,3],[2,3,1],
                   [3,1,2],[3,2,1]]

The technique we may use is based on depth 1st search (dfs). 
We may have a tuple (r,d), where r is a result that we are constructing, and 
d is data that is remaining to be used to construct r. For example assume we
have (r,d) = ([],[1,2,3]). We can then produce immediate successors
[([1],[2,3]),([2],[1,3]),([3],[1,2])], that is a permutation that begins with 1,
a permutation that begins with 2, and a permutation that begins with 3.

Assume we then have (r,d) = ([2],[1,3]). We can then produce immediate successors
[([2,1],[3]),([2,3],[1])], and from (r,d) = ([2,1],[3]) we get the successor
([2,1,3],[]), and this is a terminal node within the dfs tree. 

Therefore, at depth i in the tree we will have partial permutations of length i,
and remaining data of length n-i. All results lie at depth n.
*)

fun perm_test (_,d) = null d;
(* The state is a solution if there is no more data *)


fun remove e [] = []
   |remove e (h::t) = if e=h 
                      then remove e t
                      else h::(remove e t);

(* we need remove as a utility *)

fun perm_succ (r,d) = map (fn e => (e::r,remove e d)) d;
(* Given a node/tuple (r,d) the successors of (r,d) 
   the set of tuples (r+e,d-e), for all e in d. 
   NOTE (r+e,d-e) gives us bfs
        (e+r,d-e) gives us dfs *)


fun perm_result (r,_) = r;
(* r is always the result, and when we want it we can get it :*)

fun perm s = dfs [([],s)] perm_test perm_succ perm_result;
(* perm *)

(* ----------------------------------------------------------------------- *)

(* NOTE: we can use dfs (and bfs) to implement do_while
   In fact while is a degenerate dfs/bfs! 
   See sum_to_n below *)
   

fun sum_test (_,n) = n=0;
fun sum_succ (sum,n) = [(sum+n,n-1)];
(* That is the successor is a single tuple, namely the state vector/variables
   upd8ed. This is little different from the definition of the function
   "body" in "while test body s" where s becomes (body s) *)

fun sum_result (sum,_) = sum;
fun sum_to_n n = dfs [(0,n)] sum_test sum_succ sum_result;


(* NOTE it was also suggested that we could use dfs 
   to find an element in a binary tree (as in the lab of 11/11)
   This seems possible. What would be succ? What would be test?
   What would be result? Finally, what changes would we require to
   make to dfs/bfs to make it more applicable/efficient? (think of 
   number of solutions *)
   
(* ----------------------------------------------------------------------- *)
                          (*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 *)


(* 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 lists = dfs [([],lists)] test_cprod succ_cprod result_cprod;