Let's write a function which prints out Times (Var "n", Plus (Var "x", Var "y")) as something more like n * (x + y). The expression n * (x + y) would be written: # Times ( Var " n ", Plus ( Var " x ", Var " y " ) ) - : expr = Times ( Var " n ", Plus ( Var " x ", Var " y " ) ) Let's define a type for these expressions: type expr = | Plus of expr * expr (* a + b *) | Minus of expr * expr (* a - b *) | Times of expr * expr (* a * b *) | Divide of expr * expr (* a / b *) | Var of string (* " x ", " y ", etc. Multiply them out symbolically to get n * x + n * y. We wish to represent simple mathematical expressions like n * (x + y) and Similar functions can be written to look up values in a dictionary, to convertĪ list of pairs to or from a tree dictionary and so on. It is known as a binary search tree: # let rec insert ( k, v ) = function | Leaf -> Node ( Leaf, ( k, v ), Leaf ) | Node ( l, ( k', v' ), r ) -> if k k' then Node ( l, ( k', v' ), insert ( k, v ) r ) else Node ( l, ( k, v ), r ) val insert : 'a * 'b -> ( 'a * 'b ) tree -> ( 'a * 'b ) tree = Larger key, we have a data structure for dictionaries which performs better Insist that the keys are unique and that a smaller key is always left of a Instead of integers, we could build a tree of key-value pairs. Let's try our new functions out: # let all = total t val all : int = 10 # let flipped = flip t val flipped : int tree = Node ( Node ( Leaf, 4, Node ( Leaf, 3, Leaf ) ), 2, Node ( Leaf, 1, Leaf ) ) # t = flip flipped - : bool = true Here, flip is polymorphic while total operates only on trees of type int tree. Pattern matching on our new constructors: # let rec total = function | Leaf -> 0 | Node ( l, x, r ) -> total l + x + total r val total : int tree -> int = # let rec flip = function | Leaf -> Leaf | Node ( l, x, r ) -> Node ( flip r, x, flip l ) val flip : 'a tree -> 'a tree = Now we can write recursive and polymorphic functions over these trees, by In our example, we built an integer tree, but any type can be A Node holds a left tree, a value of type 'aĪnd a right tree. Notice that we give the type parameter 'a before the type name (if there is Here is an OCaml data typeįor a binary tree carrying any kind of data: # type 'a tree = | Leaf | Node of 'a tree * 'a * 'a tree type 'a tree = Leaf | Node of 'a tree * 'a * 'a tree # let t = Node ( Node ( Leaf, 1, Leaf ), 2, Node ( Node ( Leaf, 3, Leaf ), 4, Leaf ) ) val t : int tree = Node ( Node ( Leaf, 1, Leaf ), 2, Node ( Node ( Leaf, 3, Leaf ), 4, Leaf ) ) Type definition giving a name for the record, and names for each of its fields,Īnd their types: # type point = ĭata types may be polymorphic as well as recursive. We have records, which are like labeled tuples. Next, we have tuples, which collect a fixed number of elements together: # ( 5.0, 6.5 ) - : float * float = ( 5. Number of elements of like type: # - : 'a list = # - : int list = # ] - : int list list = ] # - : bool list = First, we have lists which are ordered collections of any Let's recap the built-in compound data types we can use in OCaml toĬombine such values. We have already seen simple data types such as int, float, string, andīool. In this tutorial we learn how to build our own types in OCaml, and how to writeįunctions which process this new data.
0 Comments
Leave a Reply. |