Pattern MatchingPattern Matchingldots Pattern Matchingldots Pattern Matchingldots Pattern Matchingldots Pattern Matchingldots Pattern Matching -- Integer PatternsPattern Matching -- List PatternsThe { t sumlist} FunctionThe { t length} Function RevisitedThe { t fact} Function RevisitedSummaryHomeworkHomeworkldots Homeworkldots Homeworkldots520—Spring 2005—13CSc 520Principles of ProgrammingLanguages13: Haskell — PatternsChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—13Pattern MatchingHaskell has a notation (called patterns) for definingfunctions that is more convenient than conditional(if-then-else) expressions.Patterns are particularly useful when the function hasmore than two cases.Pattern Syntax:function name pattern 1 = expression 1function name pattern 2 = expression 2· · ·function name pattern n = expression n[2]520—Spring 2005—13Pattern Matching...fact n = if n == 0 then1elsen * fact (n-1)fact Revisited:fact :: Int -> Intfact 0 = 1fact n = n * fact (n-1)[3]520—Spring 2005—13Pattern Matching...Pattern matching allows us to have alternativedefinitions for a function, depending on the format of theactual parameter. Example:isNice "Jenny" = "Definitely"isNice "Johanna" = "Maybe"isNice "Chris" = "No Way"[4]520—Spring 2005—13Pattern Matching...We can use pattern matching as a design aid to help usmake sure that we’re considering all possible inputs.Pattern matching simplifies taking structured functionarguments apart. Example:fun (x:xs) = x ⊕ fun xs⇔fun xs = head xs ⊕ fun (tail xs)[5]520—Spring 2005—13Pattern Matching...When a function f is applied to an argument, Haskelllooks at each definition off until the argument matchesone of the patterns.not True = Falsenot False = True[6]520—Spring 2005—13Pattern Matching...In most cases a function definition will consist of anumber of mutually exclusive patterns, followed by adefault (or catch-all) pattern:diary "Monday" = "Woke up"diary "Sunday" = "Slept in"diary anyday = "Did something else"diary "Sunday" ⇒ "Slept in"diary "Tuesday"⇒ "Did something else"[7]520—Spring 2005—13Pattern Matching – Integer PatternsThere are several kinds of integer patterns that can beused in a function definition.PatternSyntax Example Descriptionvariable var_name fact n = · · · n matches any ar-gumentconstantliteral fact 0 = · · · matches the valuewildcard_ five _ = 5 _ matches any ar-gument(n+k) pat.(n+k) fact (n+1) = · · · (n+k) matchesany integer ≥ k[8]520—Spring 2005—13Pattern Matching – List PatternsThere are also special patterns for matching and (takingapart) lists.PatternSyntax Example Descriptioncons (x:xs) len (x:xs) = · · · matches non-empty listempty[ ] len [ ] = 0 matches the empty listone-elem[x] len [x] = 1 matches a list with ex-actly 1 element.two-elem[x,y] len [x,y] = 2 matches a list with ex-actly 2 elements.[9]520—Spring 2005—13The sumlist FunctionUsing conditional expr:sumlist :: [Int] -> Intsumlist xs = if xs == [ ] then 0else head xs + sumlist(tail xs)Using patterns:sumlist :: [Int] -> Intsumlist [ ] = 0sumlist (x:xs) = x + sumlist xsNote that patterns are checked top-down! The orderingof patterns is therefore important.[10]520—Spring 2005—13The length Function RevisitedUsing conditional expr:len :: [Int] -> Intlen s = if s == [ ] then 0 else 1 + len (tail s)Using patterns:len :: [Int] -> Intlen [ ] = 0len ( :xs) = 1 + len xsNote how similar len and sumlist are. Manyrecursive functions on lists will have this structure.[11]520—Spring 2005—13The fact Function RevisitedUsing conditional expr:fact n = if n == 0 then 1 else n * fact (n-1)Using patterns:fact’ :: Int -> Intfact’ 0 = 1fact’ (n+1) = (n+1) * fact’ nAre fact and fact’ identical?fact (-1) ⇒ Stack overflowfact’ (-1) ⇒ Program ErrorThe second pattern in fact’ only matches positiveintegers (≥ 1).[12]520—Spring 2005—13SummaryFunctional languages use recursion rather than iterationto express repetition.We have seen two ways of defining a recursive function:using conditional expressions (if-then-else) orpattern matching.A pattern can be used to take lists apart without havingto explicitly invoke head and tail.Patterns are checked from top to bottom. They shouldtherefore be ordered from specific (at the top) togeneral (at the bottom).[13]520—Spring 2005—13HomeworkDefine a recursive function addints that returns thesum of the integers from 1 up to a given upper limit.Simulate the execution of addints 4.addints :: Int -> Intaddints a = · · ·? addints 515? addints 23[14]520—Spring 2005—13Homework...Define a recursive function member that takes twoarguments – an integer x and a list of integers L – andreturnsTrue if x is an element in L.Simulate the execution of member 3 [1,4,3,2].member :: Int -> [Int] -> Boolmember x L =· · ·? member 1 [1,2,3]True? member 4 [1,2,3]False[15]520—Spring 2005—13Homework...Write a recursive function memberNum x L whichreturns the number of times x occurs in L.Use memberNum to write a function unique L whichreturns a list of elements from L that occurs exactlyonce.memberNum :: Int -> [Int] -> Intunique :: [Int] -> Int? memberNum 5 [1,5,2,3,5,5]3? unique [2,4,2,1,4]1[16]520—Spring 2005—13Homework...Ackerman’s function is defined for nonnegative integers:A(0, n) = n + 1A(m, 0) = A(m − 1, 1)A(m, n) = A(m − 1, A(m, n − 1))Use pattern matching to implement Ackerman’sfunction.Flag all illegal inputs using the built-in function error Swhich terminates the program and prints the string S.ackerman :: Int -> Int -> Intackerman 0 5 ⇒ 6ackerman (-1) 5 ⇒
View Full Document
Unlocking...