CSc 520Principles of Programming Languages13: Haskell — PatternsChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Pattern Matching• Haskell has a notation (called patterns) for defining functions that is more convenient than conditional(if-then-else) expressions.• Patterns are particularly useful when the function has more than two cases.Pattern Syntax:function name pattern 1 = expression 1function name pattern 2 = expression 2· · ·function name pattern n = expression n2 Pattern Matching. . .fact n = if n == 0 then1elsen * fact (n-1)fact Revisited:fact :: Int -> Intfact 0 = 1fact n = n * fact (n-1)13 Pattern Matching. . .• Pattern matching allows us to have alternative definitions for a function, depending on the format ofthe actual parameter. Example:isNice "Jenny" = "Definitely"isNice "Johanna" = "Maybe"isNice "Chris" = "No Way"4 Pattern Matching. . .• We can use pattern matching as a design aid to help us make sure that we’re considering all possibleinputs.• Pattern matching simplifies taking structured function arguments apart. Example:fun (x:xs) = x ⊕ fun xs⇔fun xs = head xs ⊕ fun (tail xs)5 Pattern Matching. . .• When a function f is applied to an argument, Haskell looks at each definition of f until the argumentmatches one of the patterns.not True = Falsenot False = True6 Pattern Matching. . .• In most cases a function definition will consist of a number of mutually exclusive patterns, followed bya default (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 Pattern Matching – Integer Patterns• There are several kinds of integer patterns that can be used in a function definition.Pattern Syntax Example Descriptionvariable var name fact n = · · · n matches any argu-mentconstant literal fact 0 = · · · matches the valuewildcard five = 5 matches any argu-ment(n+k) pat. (n+k) fact (n+1) = · · · (n+k) matches any in-teger ≥ k28 Pattern Matching – List Patterns• There are also special patterns for matching and (taking apart) lists.Pattern Syntax 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 exactly 1element.two-elem [x,y] len [x,y] = 2 matches a list with exactly 2elements.9 The 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 xs• Note that patterns are checked top-down! The ordering of patterns is therefore important.10 The 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 xs• Note how similar len and sumlist are. Many recursive functions on lists will have this structure.11 The 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’ n3• Are fact and fact’ identical?fact (-1) ⇒ Stack overflowfact’ (-1) ⇒ Program Error• The second pattern in fact’ only matches positive integers (≥ 1).12 Summary• Functional languages use recursion rather than iteration to express repetition.• We have seen two ways of defining a recursive function: using conditional expressions (if-then-else)or pattern matching.• A pattern can be used to take lists apart without having to explicitly invoke head and tail.• Patterns are checked from top to bottom. They should therefore be ordered from specific (at the top)to general (at the bottom).13 Homework• Define a recursive function addints that returns the sum of the integers from 1 up to a given upperlimit.• Simulate the execution ofaddints 4.addints :: Int -> Intaddints a = · · ·? addints 515? addints 2314 Homework. . .• Define a recursive function member that takes two arguments – an integer x and a list of integers L –and returns True 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]False415 Homework. . .• Write a recursive function memberNum x L which returns the number of times x occurs in L.• Use memberNum to write a function unique L which returns 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]116 Homework. . .• 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’s function.• Flag all illegal inputs using the built-in function error S which terminates the program and prints thestring S.ackerman :: Int -> Int -> Intackerman 0 5 ⇒ 6ackerman (-1) 5 ⇒
View Full Document
Unlocking...