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     ! 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.