1(* Intset -- applicative sets of integers *) 2(* From SML/NJ lib 0.2, copyright 1993 by AT&T Bell Laboratories *) 3(* Original implementation due to Stephen Adams, Southampton, UK *) 4 5signature Intset = 6sig 7 8type intset 9 10exception NotFound 11 12val empty : intset 13val singleton : int -> intset 14val add : intset * int -> intset 15val addList : intset * int list -> intset 16val isEmpty : intset -> bool 17val equal : intset * intset -> bool 18val isSubset : intset * intset -> bool 19val member : intset * int -> bool 20val delete : intset * int -> intset 21val numItems : intset -> int 22val union : intset * intset -> intset 23val intersection : intset * intset -> intset 24val difference : intset * intset -> intset 25val listItems : intset -> int list 26val app : (int -> unit) -> intset -> unit 27val revapp : (int -> unit) -> intset -> unit 28val foldr : (int * 'b -> 'b) -> 'b -> intset -> 'b 29val foldl : (int * 'b -> 'b) -> 'b -> intset -> 'b 30val find : (int -> bool) -> intset -> int option 31 32end 33 34(* 35 [intset] is the type of sets of integers. 36 37 [empty] is the empty set of integers. 38 39 [singleton i] is the singleton set containing i. 40 41 [add(s, i)] adds item i to set s. 42 43 [addList(s, xs)] adds all items from the list xs to the set s. 44 45 [isEmpty s] returns true if and only if the set is empty. 46 47 [equal(s1, s2)] returns true if and only if the two sets have the 48 same elements. 49 50 [isSubset(s1, s2)] returns true if and only if s1 is a subset of s2. 51 52 [member(s, i)] returns true if and only if i is in s. 53 54 [delete(s, i)] removes item i from s. Raises NotFound if i is not in s. 55 56 [numItems s] returns the number of items in set s. 57 58 [union(s1, s2)] returns the union of s1 and s2. 59 60 [intersection(s1, s2)] returns the intersectionof s1 and s2. 61 62 [difference(s1, s2)] returns the difference between s1 and s2 (that 63 is, the set of elements in s1 but not in s2). 64 65 [listItems s] returns a list of the items in set s, in increasing 66 order. 67 68 [app f s] applies function f to the elements of s, in increasing 69 order. 70 71 [revapp f s] applies function f to the elements of s, in decreasing 72 order. 73 74 [foldl f e s] applies the folding function f to the entries of the 75 set in increasing order. 76 77 [foldr f e s] applies the folding function f to the entries of the 78 set in decreasing order. 79 80 [find p s] returns SOME i, where i is an item in s which satisfies 81 p, if one exists; otherwise returns NONE. 82*) 83