Elements of ML Programming, 2nd Edition (ML97) |

type 'a setOfSets = 'a list list;

type ('d, 'r) mapTree = ('d * 'r) btree;Then, we can define the desired tree by

val t1 = Node(("a",1), Empty, Empty): (string, int) mapTree;

open TextIO; datatype intOrEof = Eof | Int of int; fun digit(c) = c >= #"0" andalso c <= #"9"; fun startInt(file) = startInt1(file, input1(file)) and startInt1(file, NONE) = Eof | startInt1(file, SOME c) = if digit(c) then Int(ord(c)-ord(#"0")) else startInt(file); fun finishInt(i,file) = if i = Eof then Eof else finishInt1(i,file,input1(file)) and finishInt1(i, file, NONE) = i | finishInt1(i as Int(j), file, SOME c) = if digit(c) then finishInt(Int(10*j+ord(c)-ord(#"0")), file) else i; fun getInt(file) = finishInt(startInt(file), file) fun sumInts1(file) = let val i = getInt(file) in if i = Eof then 0 else let val Int(j) = i in j + sumInts1(file) end end; fun sumInts(filename) = sumInts1(openIn(filename));Download this program

datatype suit = Club | Heart | Diamond | Spade;

datatype thing = Int of int | Thing of thing listHere is a typical value of the datatype

Thing([Int(1), Thing([Int(2)]), Int(3)]);

type 'node graph = ('node * 'node list) list; exception NotANode; (* succ(a,G) looks up the list of successors of node a in graph G *) fun succ(a,nil) = raise NotANode | succ(a,(b,L)::tail) = if a=b then L else succ(a,tail); (* member(a,L) determines whether a is on list L *) fun member(a,nil) = false | member(a,b::bs) = if a=b then true else member(a,bs); (* search1(L,R,G) finds all the nodes reachable from any of the list of nodes L in graph G, but does not search from the set R of nodes that have already been reached. R is included in the set of reached nodes that is eventually returned. *) fun search1(nil,R,G) = R | search1(x::xs,R,G) = if member(x,R) then search1(xs,R,G) else (* x is a new node, never before seen *) search1(succ(x,G)@xs, x::R, G); (* search(a,G) finds the set of nodes reachable from a in graph G *) fun search(a,G) = search1([a],nil,G);Download this program

fun lookup lt Empty a = raise Missing | lookup lt (Node((c,b),left,right)) a = if lt(a,c) then lookup lt left a else if lt(c,a) then lookup lt right a else (* a=c *) b;

val lookup1 = lookup (op < : real*real->bool);and similarly for the other two functions. An alternative is

val lookup1 = lookup (fn (x:real,y) => x<y);using an anonymous function. However, beware

val lookup1 = lookup (op <:real*real->bool);which, although it looks almost identical to our first solution, is an error. Do you see why?

val lookupS = lookup (op <) ( Node(16, Node(4, Node(1,Empty,Empty), Node(9,Empty,Empty) ), Node(36, Node(25,Empty,Empty), Empty ) ) );Download this program

fun isOn (Node(a,nil)) x = (a=x) | isOn (Node(a,t::ts)) x = isOn t x orelse isOn (Node(a,ts)) x;For part (b), we found it more convenient to put the element

fun isOn x (Node(a,L)) = (a=x) orelse foldr (fn (x,y) => x orelse y) false (map (isOn x) L);If

fun preOrder(Node(a,nil)) = [a] | preOrder(Node(a,t::ts)) = a :: preOrder(t) @ (tl(preOrder(Node(a,ts))));

fun preOrder1(Node(a,nil), L) = a::L | preOrder1(Node(a,t::ts), L) = a :: preOrder1(t, tl(preOrder1(Node(a,ts),L))); fun preOrder(T) = preOrder1(T,nil);Function