(* MODIFIED FROM BEN GOLDBERG'S LECTURE NOTES *) (* USER-DEFINED TYPES *) type mytype = bool list ; (* makes "mytype" a synonym for "bool list" *) type mytype = bool list fun one (x:mytype) = hd x; val one = fn : mytype -> bool (* To define a brand new type, we use the "datatype" construct *) datatype stoplight = red | green | yellow ; datatype stoplight = green | red | yellow (* The order doesn't matter, so the interpreter alphabetizes.) val x = red; val x = red : stoplight (* These literals, "green", "read", and "yellow" can be used as patterns *) fun drive red = "stop" | drive green = "go" | drive yellow = "go faster" ; val drive = fn : stoplight -> string drive yellow; val it = "go faster" : string (* Recursive datatypes *) datatype tree = leaf of int | node of tree * tree ; val t = node(node(leaf 2, leaf 3), leaf 5); val t = node (node (leaf #,leaf #),leaf 5) : tree (* t is the tree node ---> node ---> leaf 2 | | | |-> leaf 3 | |-> leaf 5 *) (* The # mark is just an indicator that the structure continues past the maximum default depth for the printer *) (* Note: "leaf" and "node" are both little functions. leaf N is a function of type fn : int -> tree that returns the structure (leaf N) node (E1,E2) is a function of type expr * expr -> expr that returns the structure (node E1 E2). *) (* Here's a function that returns the "frontier" of a tree, namely the list of integers at the leaves of a tree *) fun frontier (leaf x) = [x] | frontier (node (l,r)) = frontier l @ frontier r ; val frontier = fn : tree -> int list frontier t; val it = [2,3,5] : int list (* Can also define polymorphic datatypes *) datatype 'a tree = leaf of 'a | node of 'a tree * 'a tree ; datatype 'a tree = leaf of 'a | node of 'a tree * 'a tree leaf 3; val it = leaf 3 : int tree leaf true; val it = leaf true : bool tree node(leaf "hello", leaf "goodbye") ; val it = node (leaf "hello",leaf "goodbye") : string tree (* The following is illegal, since in a given data structure all instances of 'a must be the same type *) node(leaf 2, leaf false); stdIn:7.38-9.26 Error: operator and operand don't agree [literal] operator domain: int tree * int tree operand: int tree * bool tree in expression: node (leaf 2,leaf false) fun frontier (leaf x) = [x] | frontier (node (l,r)) = frontier l @ frontier r ; val frontier = fn : 'a tree -> 'a list - frontier (node(leaf "hello", leaf "goodbye")); val it = ["hello","goodbye"] : string list frontier(leaf 5); val it = [5] : int list (* Expression tree *) datatype expr = Numeral of int | Plus of expr * expr | Times of expr * expr; fun eval (Numeral n) = n | eval (Plus (e1, e2)) = (eval e1) + (eval e2) | eval (Times (e1, e2)) = (eval e1) * (eval e2); val t = Times (Plus (Numeral 3, Numeral 5), Numeral 7); val t = Times (Plus (Numeral #,Numeral #),Numeral 7) : expr eval t; val it = 56 : int; (* Tree with any number of children *) datatype 'a otree = oleaf of 'a | onode of 'a otree list; val t = onode [oleaf 3, oleaf 4, onode [oleaf 2]]; (* The leaves of a tree may themselves be trees *) val t = node(leaf(node(leaf 3,leaf 4)),leaf(leaf(5))); val t = node (leaf (node (#,#)),leaf (leaf 5)) : int tree tree (* Corresponds to the structure _____________________ | Node ---> Leaf 3 | Node ---> Leaf | | | | | |-> Leaf 4 | | |____________________| | | ____________________ |-> Leaf | Leaf 5 | |__________________| *)