Slide 1ReviewRecursive datatypesOptions are datatypesLists are datatypesWhy pattern-matchingEach-of typesExampleVal-binding patternsBetter exampleA new way to goFunction-argument patternsHmmThe truth about functionsOne-of types in function bindingsMore sugarNested patternsUseful example: zip/unzip 3 lists(Most of) the full definitionCSE341: Programming LanguagesLecture 5Pattern-MatchingDan GrossmanFall 2011ReviewDatatype bindings and pattern-matching so far:Adds type t and constructors Ci of type ti->t –Ci v is a value•Evaluate e to a value•If pi is the first pattern to match the value, then result is evaluation of ei in environment extended by the match•Pattern Ci(x1,…,xn) matches value Ci(v1,…,vn) and extends the environment with x1 to v1 … xn to vn•This lecture: many more kinds of patterns and ways to use themFall 2011 2CSE341: Programming Languagesdatatype t = C1 of t1 | C2 of t2 | … | Cn of tncase e of p1 => e1 | p2 => e2 | … | pn => enRecursive datatypesDatatype bindings can describe recursive structures–Arithmetic expressions from last lecture–Linked lists, for example:Fall 2011 3CSE341: Programming Languagesdatatype my_int_list = Empty | Cons of int * my_int_listval x = Cons(4,Cons(23,Cons(2008,Empty)))fun append_my_list (xs,ys) = case xs of Empty => ys | Cons(x,xs’) => Cons(x, append_my_list(xs’,ys)Options are datatypesOptions are just a predefined datatyping binding–NONE and SOME are constructors, not just functions–So use pattern-matching not isSome and valOfFall 2011 4CSE341: Programming Languagesfun inc_or_zero intoption = case intoption of NONE => 0 | SOME i => i+1Lists are datatypesDon’t use hd, tl, or null either–[] and :: are constructors too –(strange syntax, particularly infix)Fall 2011 5CSE341: Programming Languagesfun sum_list intlist = case intlist of [] => 0 | head::tail => head + sum_list tailfun append (xs,ys) = case xs of [] => ys | x::xs’ => x :: append(xs’,ys)Why pattern-matching•Pattern-matching is better for options and lists for the same reasons as for all datatypes–No missing cases, no exceptions for wrong variant, etc.•We just learned the other way first for pedagogy•So why are null and tl predefined then?–For passing as arguments to other functions (next week)–Because sometimes they’re really convenient–But not a big deal: could define them yourself with caseFall 2011 6CSE341: Programming LanguagesEach-of typesSo far have used pattern-matching for one of types because we needed a way to access the valuesPattern matching also works for records and tuples:–The pattern (x1,…,xn) matches the tuple value (v1,…,vn)–The pattern {f1=x1, …, fn=xn} matches the record value {f1=v1, …, fn=vn} (and fields can be reordered)Fall 2011 7CSE341: Programming LanguagesExampleThis is poor style, but based on what I told you so far, the only way to use patterns–Works but poor style to have one-branch casesFall 2011 8CSE341: Programming Languagesfun sum_triple triple = case triple of (x, y, z) => x + y + zfun sum_stooges stooges = case stooges of {larry=x, moe=y, curly=z} => x + y + zVal-binding patterns•New feature: A val-binding can use a pattern, not just a variable–(Turns out variables are just one kind of pattern, so we just told you a half-truth in lecture 1)•This is great for getting (all) pieces out of an each-of type–Can also get only parts out (see the book or ask later)•Usually poor style to put a constructor pattern in a val-binding–This tests for the one variant and raises an exception if a different one is there (like hd, tl, and valOf)Fall 2011 9CSE341: Programming Languagesval p = eBetter exampleThis is reasonable style–Though we will improve it one more time next–Semantically identical to one-branch case expressionsFall 2011 10CSE341: Programming Languagesfun sum_triple triple = let val (x, y, z) = triple in x + y + z endfun sum_stooges stooges = let val {larry=x, moe=y, curly=z} = stooges in x + y + z endA new way to go•For homework 2:–Do not use the # character–You won’t need to write down any explicit types•These are related–Type-checker can use patterns to figure out the types–With just #foo it can’t “guess what other fields”Fall 2011 11CSE341: Programming LanguagesFunction-argument patternsA function argument can also be a pattern–Match against the argument in a function callExamples:Fall 2011 12CSE341: Programming Languagesfun f p = efun sum_triple (x, y, z) = x + y + zfun sum_stooges {larry=x, moe=y, curly=z} = x + y + zHmmA function that takes one triple of type int*int*int and returns an int that is their sum:Fall 2011 13CSE341: Programming LanguagesA function that takes three int arguments and returns an int that is their sumfun sum_triple (x, y, z) = x + y + zfun sum_triple (x, y, z) = x + y + zSee the difference? (Me neither.) The truth about functions•In ML, every function takes exactly one argument (*)•What we call multi-argument functions are just functions taking one tuple argument, implemented with a tuple pattern in the function binding–Elegant and flexible language design•Enables cute and useful things you can’t do in Java, e.g., * “Zero arguments” is the unit pattern () matching the unit value ()Fall 2011 14CSE341: Programming Languagesfun rotate_left (x, y, z) = (y, z, x)fun rotate_right t = rotate_left(rotate_left t)One-of types in function bindingsAs a matter of taste, I personally have never loved this syntax, but others love it and you’re welcome to use it:Example:As a matter of semantics, it’s syntactic sugar for:Fall 2011 15CSE341: Programming Languagesfun f p1 = e1 | f p2 = e2 … | f pn = enfun eval (Constant i) = i | eval (Add(e1,e2)) = (eval e1) + (eval e2) | eval (Negate e1) = ~ (eval e1)fun f x = e1 case x of p1 => e1 | p2 => e2 …More sugarBy the way, conditionals are just a predefined datatype and if-expressions are just syntactic sugar for case expressionsFall 2011 16CSE341: Programming Languagesdatatype bool = true | falseif e1 then e2 else e3case e1 of true => e2 | false => e3Nested patterns•We can nest patterns as deep as we want–Just like we can nest expressions as deep as we want–Often avoids hard-to-read, wordy nested case expressions•So the full meaning of pattern-matching is to compare a pattern against a value for the “same shape” and bind variables to the “right parts”–More
View Full Document
Unlocking...