(*  Here are two of the simple AI search techniques.
    Arguments (in order):
      a list of operators (each is a condition-action pair),
      a goal (a predicate that is true when a state satisfies the goal)
      a list of open states
    Result: a state that satisfies the goal

    Notes:
    (1) these functions are undefined if the list of open states is empty
    (2) these functions are polymorphic -- i.e. independent of the exact
        manner in which states are represented
    Exercise (major): rewrite these functions so that they return the
        operator-sequence leading to the goal state
*)

fun FILTER (P,[])         = []
 |  FILTER (P,head::tail) = if (P head)
                            then head::(FILTER (P,tail))
                            else (FILTER (P,tail))
;

fun MAP_Operators ([],_) = []    (* analogous to MAP, this applies a list of
                                    operators to the same argument *)
 |  MAP_Operators ((Condition,Action)::OtherOperators,State) =
       if   (Condition State)
       then (Action State)::(MAP_Operators (OtherOperators,State))
       else (MAP_Operators (OtherOperators,State))
;

fun PRODUCT_Operators (_,[]) = []  (* a version of  PRODUCT for Operators *)
 |  PRODUCT_Operators (Ops,ArgHead::ArgTail) =
        (MAP_Operators (Ops,ArgHead))@(PRODUCT_Operators (Ops,ArgTail))
;

fun breadth_first (Operators,Goal,States) =
let
    val NewStates = PRODUCT_Operators (Operators,States)
(*    val _ = print (NewStates: int list)     *)
    val GoalStates = FILTER (Goal,NewStates)
in
    case GoalStates of
            []     => breadth_first (Operators,Goal,NewStates)
     | Solution::_ => Solution
end;


fun depth_first (Operators,Goal,HeadState::OtherStates) =
let
    val NewStates = MAP_Operators (Operators,HeadState)
(*    val _ = print (NewStates: int list)     *)
    val GoalStates = FILTER (Goal,NewStates)
in
    case NewStates of
           []     => depth_first (Operators,Goal,OtherStates)
     | NewHead::_ => if   (Goal NewHead)
                     then NewHead
                     else depth_first (Operators,Goal,NewStates@OtherStates)
end;


(* Simple example.
   States are integers.
   There are two operators, whose actions are adding 1, and doubling.
   The goal is to find an integer divisible by 4.
   From an initial state of 5, breadth-first should find either 12 (add 1 and
   double) or 20 (2 doublings), whereas depth-first should find 8.
*)

fun add1   x = x+1;
fun double x = 2*x;
fun always_true x = true;
val op1 = (always_true,add1);
val op2 = (always_true,double);
fun div_by_4 x = (x mod 4) = 0;

val bf = breadth_first ([op1,op2],div_by_4,[5]);
val df = depth_first   ([op1,op2],div_by_4,[5]);