User-defined TYPES First, we look at type abbreviations... names for types expressions using existing (built-in) types and type constructors base types: int, string, bool, real, unit, exn, instream, ostream type constructors: *, ->, list, array, ref if T1 and T2 are types, so are T1 * T2, T1 -> T2, T1 list, etc. These type expressions can be named and later used as follows: type vector = real list ; val v = [1.0, 2.0] : vector ; >> val v = [1.0, 2.0] : vector val x = [1.0, 2.0] ; >> val v = [1.0, 2.0] : real list v = x ; val it = true : bool Notice that the type def "vector" is type equivalent to "real list" so this is not a NEW type, just an abbreviation |
Polymorphic Type Definitions type ('d,'r) mapping = ('d * 'r) list ; This is make a type name for a list of pairs, each pair will contain two elements of types determined when the type is instantiated. val w1 = [("in",6), ("a",1)]; >> val words = [("in",6),("a",1)] : (string * int) list val w2 = [("in",6), ("a",1)] : (string,int) mapping ; >> val words = [("in",6),("a",1)] : (string,int) mapping These abberviations may be useful, but they are limited in power since they are just shorthand notation. |
Datatypes and Data Constructors Instead of merely defining abbreviations for type expressions, we want to create new structures (like trees, records, etc.) Datatype definitions create NEW types that are not abbreviations for any other type datatype fruit = Apple | Pear | Grape ; >> datatype fruit >> con Apple : fruit >> con Grape : fruit >> con Pear : fruit Note the interpreter says that Apple, Pear, Grape are all data constructors fun isApple(x) = (x=Apple) ; >> val it = fn : fruit -> bool isApple(Pear) ; >> val it = false : bool isApple(Banana) ; >> error: unbound variable: Banana This is essentially making Pascal-style enumerated types |
Data constructors are expressions that build values for a type. The data constructors in the previous example are simple, essentially named constants. Here is a more general form of datatype definition: datatype ('a,'b) elt = P of 'a * 'b | S of 'a ; >> datatype ('a,'b) elt >> con P : 'a * 'b -> ('a,'b) elt >> con S : 'a -> ('a,'b) elt This is something like a C union type, except it's polymorphic. The type "('a,'b) elt" is actually composed of elements from two dissimilar subtypes, denoted by constructors "P" and "S". Here, the constructors look like functions (they are not) in that they require data items of certain types in order to make items of type "elt"... this is more like the REPRESENTATION from ADT implementations val m = [("hi",1),("there"),("big",4)]; >> Error: operator and operand don't agree (tycon mismatch) >> operator domain: string * string list >> operand: string * (string * int) list >> in expression: >> ("there") :: ("big",4) :: nil val m = [P("hi",1), S("there"), P("big",4)]; >> val m = [P ("hi",1),S "there", P ("big",4)] : (string,int) elt list The interpreter picked proper instantiations for type vars 'a and 'b in the definition of ('a,'b) elt |
Using the datatype fun sumEltList(nil) = 0 | sumEltList(S(x)::L) = sumEltList(L) | sumEltList(P(x,y)::L) = y + sumEltList(L) ; >> val sumEltList = fn : ('a,int) elt list -> int sumEltList m ; >> val it = 5 : int The data constructors are used in the function code where needed to distinguish the various versions of the elements in "('a,'b)elt" This is a common programming pattern with datatypes: one alternative in the fun defn for each data constructor... that way the fun has an alternative to match any element of the type. |
Another Example: Binary trees datatype 'label btree = Empty | Node of 'label * 'label btree * 'label btree ; >> datatype 'a btree >> con Empty : 'a btree >> con Node : 'a * 'a btree * 'a btree -> 'a btree Note the interpreter renaming the type variable... Node("as",Node("a",Empty,Empty),Node("in",Empty,Empty)) ; >> val it = Node ("as", Node ("a",Empty,Empty), Node ("in",Empty,Empty)) : string btree Node(2,Node(1,Empty,Empty),Empty) ; >> val it = Node (2,Node (1,Empty,Empty),Empty) : int btree |
Mutually Recursive Datatypes Similar to defining mutually recursive functions: datatype 'lab eTree = Empty | eNode of 'lab * 'lab oTree * 'lab oTree and 'lab oTree = oNode of 'lab * 'lab eTree * 'lab eTree ; eTree has even length paths from root to each leaf. oTree has odd length paths. The Empty tree is an eTree, since path length is 0. val t1 = oNode(1,Empty,Empty); val t2 = oNode(2,Empty,Empty); val t3 = eNode(3,t1,t2); val t4 = oNode(4,t3,Empty); val t5 = eNode(5,t4,t4); |
Extended Example: Binary Search Tree datatype 'label btree = Empty | Node of 'label * 'label btree * 'label btree; (*=================================================================*) fun lower(nil) = nil | lower(c::cs) = if c>="A" andalso c<="Z" then chr(ord(c)+32)::lower(cs) else c::lower(cs); fun lt(x:string,y) = implode(lower(explode(x))) < implode(lower(explode(y))); exception EmptyTree; (*=================================================================*) (* lookup(x,T) tells whether element x is in tree T *) fun lookup(x,Empty) = false | lookup(x,Node(y,left,right)) = if x=y then true else if lt(x,y) then lookup(x,left) else (* lt(y,x) *) lookup(x,right); (* insert(x,T) returns tree T with x inserted *) fun insert(x,Empty) = Node(x,Empty,Empty) | insert(x, T as Node(y,left,right)) = if x=y then T (* do nothing; x was already there *) else if lt(x,y) then Node(y,insert(x,left),right) else (* lt(y,x) *) Node(y,left,insert(x,right)); (* deletemin(T) returns a pair consisting of the least element y in tree T and the tree that results from deleting y from T. It is an error if T is empty *) fun deletemin(Empty) = raise EmptyTree | deletemin(Node(y,Empty,right)) = (y,right) (* This is the critical case. If the left subtree is empty, then the element at the current node is the min. *) | deletemin(Node(w,left,right)) = let val (y,L) = deletemin(left) in (y, Node(w,L,right)) end; (* delete(x,T) returns tree T with element x deleted *) fun delete(x,Empty) = Empty | delete(x,Node(y,left,right)) = if lt(x,y) then Node(y,delete(x,left),right) else if lt(y,x) then Node(y,left,delete(x,right)) else (* x=y *) if left = Empty then right else if right = Empty then left else let val (z,R) = deletemin(right) in Node(z,left,R) end; fun sum(Empty) = 0 | sum(Node(a,left,right)) = a + sum(left) + sum(right); fun preOrder(Empty) = nil | preOrder(Node(a,left,right)) = [a] @ preOrder(left) @ preOrder(right) ; |
Structures General definition: structure < id > = struct < elements of structure > end Reconsider the mapping from previous examples structure Mapping = struct exception NotFound ; val create = nil ; fun lookup (d,nil) = raise NotFound | lookup (d, (e,r)::es) = if d=e then r else lookup(d,es) ; fun insert (d,r,nil) = [(d,r)] | insert (d,r,(e,s)::es) = if d=e then (d,r)::es else (e,s)::insert(d,r,es) ; end; >> structure Mapping : >> sig >> exception NotFound >> val create : 'a list >> val insert : ''a * 'b * (''a * 'b) list -> (''a * 'b) list >> val lookup : ''a * (''a * 'b) list -> 'b >> end | |
Signatures General form: sig < specs > end signature < id > = sig < specs > end Example: signature SIMAPPING = sig exception NotFound ; val create : (string * int) list ; val insert : string * int * (string * int) list -> (string * int) list val lookup : string * (string * int) list -> int end ; We can now use SIMAPPING signature to restrict the structure Mapping previously defined: structure SiMapping: SIMAPPING = Mapping Could have done it directly as well: structure SiMapping: SIMAPPING = struct exception NotFound ; val create = nil ; fun lookup (d,nil) = raise NotFound | lookup (d, (e,r)::es) = if d=e then r else lookup(d,es) ; fun insert (d,r,nil) = [(d,r)] | insert (d,r,(e,s)::es) = if d=e then (d,r)::es else (e,s)::insert(d,r,es) ; end; | |
There are 2 ways a signature can restrict a structure: (1) The sig can specify a more restrictive type for an identifier than is implicit in the structure defn (as done in SiMapping) (2) The sig can omit certain identifiers, hiding them. For example, we could create a mapping in which users could not modify the elements, by hiding "create" and "insert" sig exception NotFound; val lookup : string * (string * int) list -> int end ; | |
Accessing Names in Structures Assume we have done this: structure SiMapping: SIMPAAING = Mapping We can now access it operations and elements this way: val m = SiMapping.create ; >> val m = nil : (string * int) list val m = SiMapping.insert("in",6,m) ; >> val m = [("in",6)] : (string * int) list SiMapping.lookup("in",m) ; >> val it = 6 We can also "open" a structure and not need the dot notation: open SiMapping ; Any identifiers defined in SiMapping are now hiding previous definitions they might have had. You can still get others with explicit dot notation. Or you can selectively make abbreviations without opening: val create = SiMapping.create ; val insert = SiMapping.insert ; | |
Importing into Structures We can use in a structure any identifiers that are defined at the time the structure is defined. Nice, but leads to problems: fun lt (x:string, y) = (* some defn *) >> val lt = fn : string * string -> bool structure StringBST = struct datatype 'label btree = Empty | Node of 'label * 'label btree * 'label btree ; val create = Empty ; fun insert(x,T) = (* code *) fun lookup(x,T) = (* code *) exception EmptyTree ; fun deletemin(T) = (* code *) fun delete(x,T) = (* code *) end ; In this case, the "lt" function is not part of the structure, but it is used by the various lookup functions, etc.... if it were not defined when StringBST was defined, error. We can now instantiate StringBST different ways (restrict with sigs) and have it work with different versions of lt... Note: if "lt" were changed after a version of StringBST were defined, the version of "lt" that existed when structure is defined stays in force for the structure. Thus, the meaning of a structure could differ, depending on what code preceeds it... not the best way
| |
Functors Functors help us with encapsulation and generality of structures. They address the anomalies just seen for importing into structures, for example. signature TOTALORDER = sig eqtype elt ; val lt : elt * elt -> bool ; end ; functor MakeBST ( Lt: TOTALORDER ) : sig open Lt ; type 'label btree ; exception EmptyTree ; val create : elt btree ; val lookup : elt * elt btree -> bool ; val insert : elt * elt btree -> elt btree ; val deletemin : elt btree -> elt * elt btree ; val delete : elt * elt btree -> elt btree end = struct open Lt ; datatype 'label btree = Empty | Node of 'label * 'label btree * 'label btree ; val create = Empty ; fun insert(x,T) = (* code *) ; fun lookup(x,T) = (* code *) ; exception EmptyTree ; fun deletemin(T) = (* code *) ; fun delete(x,T) = (* code *) ; end ; >> functor MakeBST: |