CSE341, Fall 2011, Lecture 5 SummaryStandard Disclaimer: This lecture summary is not necessarily a complete substitute for attending class,reading the associated code, etc. It is designed to be a useful resource for students who attended class andare later reviewing the material.While the last lecture introduced the basics of datatype bindings and case expressions, this lecture:• Gives a more precise semantics• Demonstrates that lists and options are just (polymorphic) datatypes• Shows that pattern-matching can also be used for each-of types• Shows that val bindings and function arguments also use patterns, and in fact every function takesexactly one argument• Patterns can be nested inside other patterns, which generalizes the definition of pattern-matching• Gives examples showing the benefits of all these featuresA precise definition of things so farWe can summarize what we know about datatypes and pattern matching from the previous lecture as follows:The bindingdatatype t = C1 of t1 | C2 of t2 | ... | Cn of tnintroduces a new type t and each constructor Ci is a function of type ti->t. One omits the “of ti” for avariant that “carries nothing.” To “get at the pieces” of a t we use a case expression:case e of p1 => e1 | p2 => e2 | ... | pn => enA case expression evaluates e to a value v, finds the first pattern pi that matches e, and evaluates ei toproduce the result for the whole case expression. So far, patterns have looked like Ci(x1,...,xn) where Ciis a constructor of type t1 * ... * tn -> t (or just Ci if Ci carries nothing). Such a pattern matches avalue of the form Ci(v1,...,vn) and binds each xi to vi for evaluating the corresponding ei.Lists and options are datatypesBecause datatype definitions can be recursive, we can use them to create our own types for lists. For example,this binding works well for a linked list of integers:datatype my_int_list = Empty| Cons of int * my_int_listWe can use the constructors Empty and Cons to make values of my_int_list and we can use case expressionsto use such values:val one_two_three = Cons(1,Cons(2,Cons(3,Empty)))fun append_mylist (l1,l2) =case l1 ofEmpty => l2| Cons(hd,tl) => Cons(hd, append_mylist(tl,l2))1It turns out the lists and options “built in” (i.e., predefined with some special syntactic support) are justdatatypes. As a matter of style, it is better to use the built-in widely known feature than to invent your own.More importantly, it is better style to use pattern-matching for accessing list and option values, not thefunctions null, hd, tl, isSome, and valOf we saw previously. (We used them because we had not learnedpattern-matching yet and we didn’t want to delay practicing our functional-programming skills.)For options, all you need to know is SOME and NONE are constructors, which we use to create values (just likebefore) and in patterns to access the values. Here is a short example of the latter:fun inc_or_zero intoption =case intoption ofNONE => 0| SOME i => i+1The story for lists is similar with a few convenient syntactic peculiarities: [] really is a constructor thatcarries nothing and :: really is a constructor that carries two things, but :: is unusual because it is an infixoperator (it is placed between its two operands), both when creating things and in patterns:fun sum_list intlist =case intlist of[] => 0| head::tail => head + sum_list tailfun append (l1,l2) =case l1 of[] => l2| head::tail => head :: append(tail,l2)Notice here head and tail are nothing but local variables introduced via pattern-matching. We can useany names for the variables we want. We could even use hd and tl — doing so would simply shadow thefunctions predefined in the outer environment.The reasons why you should usually prefer pattern-matching for accessing lists and options instead of func-tions like null and hd is the same as for datatype bindings in general: you can’t forget cases, you can’tapply the wrong function, etc. So why does the ML environment predefine these functions if the approachis inferior? In part, because they are useful for passing as arguments to other functions, a major topic stilla couple lectures ahead of us.Other than the strange syntax of [] and ::, the only thing that distinguishes the built-in lists and optionsfrom our example datatype bindings is that the built-in ones are polymorphic – they can be used for carryingvalues of any type, as we have seen with int list, int list list, (bool * int) list, etc. You can dothis for your own datatype bindings too, and indeed it is very useful. While we will not focus on using thisfeature (i.e., you’re not responsible for knowing how to do it), there is nothing very complicated about it.For example, this is exactly how options are defined in the built-in environment:datatype ’a option = NONE | SOME of ’aPattern-matching for each-of types, and the truth about val-bindings and function argumentsSo far we have used pattern-matching for one-of types, but we can use them for each-of types also. Givena record value {f1=v1,...,fn=vn}, the pattern {f1=x1,...,fn=xn} matches and binds xi to vi. As youmight expect, the order of fields in the pattern does not matter. As before, tuples are syntactic sugar forrecords, so the tuple value (v1,...,vn) matches the pattern (x1,...,xn). So we could write this functionfor summing the three parts of an int * int * int:2fun sum_triple triple =case triple of(x,y,z) => z + y + xAnd a similar example with records could look like this:fun sum_stooges triple =case triple of{larry=x,curly=y,moe=z} => z + y + xHowever, a case-expression with one branch is poor style — it just looks odd since the purpose of suchexpressions is to distinguish cases, plural. So how should we use pattern-matching for each-of types, whenwe know that a single pattern will definitely match so we are using pattern-matching just for the convenientextraction of values? It turns out you can use patterns in val-bindings too! So this approach is better style:fun sum_stooges triple =let val {larry=x,curly=y,moe=z} = tripleinx + y + zendfun sum_triple triple =let val (x,y,z) = tripleinx + y + zendBut actually we can do better still: Just like a pattern can be used in a val-binding to bind variables (e.g.,x, y, and z) to the various pieces of the expression (e.g., triple), we can use a pattern when defining afunction binding and the pattern will be used to introduce bindings by matching against the value passedwhen the function is called. So
View Full Document
Unlocking...