Return to mandc.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / doc / examples / missionaries

Annotation of researchv10no/cmd/sml/doc/examples/missionaries/mandc.sml, revision 1.1.1.1

1.1       root        1: (* Missionaries and canabals state space *)
                      2: structure MandC =
                      3: struct
                      4: 
                      5:   datatype loc = LEFT | RIGHT  (* location of boat *)
                      6: 
                      7:   type sit = {mis:int,can:int,boat:loc}
                      8:   type state = sit list
                      9: 
                     10:   (* sit, short for situation, represents number of missionaries and canabals
                     11:        where the boat is, and the location of the boat.
                     12:      state is a list of situation, representing a history of moves *)
                     13: 
                     14:   fun member(s, []:state) = false
                     15:     | member(s,s'::rest) = s = s' orelse member(s,rest)
                     16: 
                     17:   (* safe checks that there are at least as many missionaries as canabals
                     18:      where ever they are mixed, and also checks that the latest situation
                     19:      hasn't occurred before in the state *)
                     20:   fun safe((new as {mis,can,...})::old : state) = 
                     21:       (mis=0 orelse (mis>=can andalso (3-mis = 0 orelse 3-mis >= 3-can)))
                     22:       andalso not(member(new,old))
                     23: 
                     24:   fun printSit (h:string) ({mis,can,boat}: sit) =
                     25:         (print h; print mis;
                     26:          print " "; print can;
                     27:          print " "; case boat of LEFT => print "LEFT" | _ => print "RIGHT";
                     28:         print "\n")
                     29: 
                     30:   fun goal(s as {mis=3,can=3,boat=RIGHT}::_ : state) = 
                     31:         (app (fn sit => printSit "% " sit) (rev s); true)
                     32:     | goal(sit::_) =
                     33:        (printSit "? " sit; false)
                     34: 
                     35:   (* possible configurations of passengers on the canoe, (missionaries,canabals) *)
                     36:   val passengers = [(2,0),(1,1),(0,2),(1,0),(0,1)]
                     37: 
                     38:   fun cross LEFT = RIGHT
                     39:     | cross RIGHT = LEFT
                     40: 
                     41:   (* moves generates list of possible successors of its state argument *)
                     42:   fun moves (s as {mis,can,boat}::_) = 
                     43:       let fun mv [] = []
                     44:            | mv ((m,c)::rest) =
                     45:                if mis >= m andalso can >= c 
                     46:                then ({mis=3-mis+m,can=3-can+c,boat=cross(boat)}::s)::mv rest
                     47:                else mv rest
                     48:        in fold (fn (s,l) => if safe s then s::l else l) (mv passengers) []
                     49:       end
                     50: 
                     51:   val initial : state = [{mis=3, can=3, boat=LEFT}]  (* initial state *)
                     52: 
                     53: end (* MandC *)
                     54: 
                     55: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.