Patterns and Tuples and Lists (Oh, My!)
Patterns and Tuples and Lists (Oh, My!)
Prof. Susan Older
7 February 2017
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 1 / 13
Another Look at Formal Parameters
Recall from long ago:
simple :: Int -> Int -> Int
simple a b = a + 3*b
In the definition above, a and b are the formal parameters of simple.
They act as names for input values that are passed into the function.
Names/variables are simply one sort of pattern that can be used to
represent the input that’s passed into a function.
The simplest sorts of patterns are:
1 Names, such as a, b, big, item
2 Constants, such as 0, 37, True
3 Wildcard (“don’t care”), represented as an underscore ( )
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 2 / 13
Patterns and Multiple-Equation Definitions (Take One)
We can define functions by using multiple equations:
myFun :: Int -> Int -> Int
myFun 0 _ = 15
myFun x 0 = x+1
myFun x y = x*x + y
The Evaluation Rule:
Use the first equation whose patterns are matched by the input.
(But what does that mean?)
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 3 / 13
Simple Pattern Matching
A function’s formal parameters are patterns that are matched against its
input (i.e., its actual parameters).
For now, very simple patterns (more powerful ones later):
Pattern Input that Matches Pattern Effect (if any)
Variable anything Binds input to variable
Constant
anything that evaluates
to the given constant
None
Wildcard ( ) anything None
Examples
1 Input 12*4 matches these patterns: 48, stuff,
2 Input 12*4 does not match these patterns: 47, False
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 4 / 13
Patterns and Multiple-Equation Definitions (Take Two)
Consider the following:
myFun :: Int -> Int -> Int
myFun 0 _ = 15
myFun x 0 = x+1
myFun x y = x*x + y
Use the first equation whose patterns are matched by the input.
What are the values of the following?
1 myFun (6*2) (3-(4-1)) 13
2 myFun (4-4) (2*3*4*5) 15
3 myFun (7-2) (2*6) 37
4 myFun (4-4) False Type Error!
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 5 / 13
What’s the Point of Pattern Matching?
We will see that using patterns in equations lets us:
Distinguish cases based on the structure of data
Deconstruct “complex” data into simpler components and give names
to those smaller pieces
In contrast, conditional equations distinguish cases based on true/false
properties of the data, and don’t deconstruct data.
We’ve seen two ways to combine multiple values into a single package:
1 Tuples
Contain a fixed number of items, possibly having different types
2 Lists
Contain an arbitrary number of items, all having the same type
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 6 / 13
New Types from Old: Tuples
Tuple Types
Suppose t1, t2, · · · , tn are all types. Then there is a type
(t1, t2, · · · , tn),
whose values have form (v1, v2, · · · , vn) (where vi :: ti , for each i).
Examples
(Char,Bool) has values (’A’,True) and (’#’,False).
(Int,Bool,Char,Float) has value (7,False,’M’,9.65).
(Int,Char,String,Float,Bool) has value
(7,’M’,”abcd”,9.65,True).
((Int,Char), (String,Float,Bool)) has value
((7,’M’), (“abcd”,9.65,True)).
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 7 / 13
Examples of Tuple Use
topRightQuad :: (Float,Float) -> Bool
topRightQuad (x,y) = x>0 && y>0
topHalf :: (Float, Float) -> Bool
topHalf (_,y) = y>0
scale :: Int -> (Int,Int) -> (Int,Int)
scale m (x,y) = (m*x, m*y)
minMax :: Int -> Int -> (Int, Int)
minMax a b = (min a b, max a b)
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 8 / 13
Pattern Matching Extended to Tuples
Pattern Input that Matches Pattern Effect (if any)
Variable anything Binds input to variable
Constant
any input that evaluates
to that constant
None
Wildcard ( ) anything None
( p1,p2,. . . ,pn)
each pi is pattern
( e1,e2,. . . ,en)
where each ei matches pi
componentwise effects
(y,( ,True),z) is matched by input (’R’,(45,not False),12*3):
y is matched by ’R’ (’R’ gets bound to name y)
( ,True) is matched by (45,not False)
z is matched by 12*3 (12*3 gets bound to name z)
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 9 / 13
New Types from Old: Lists
List Types
Suppose t is a type. Then [t] is the type of lists over type t.
[True,False,False,True,False] :: [Bool]
[5,10,15,24] :: [Int]
[(5,True),(10,False),(13,True)] :: [(Int,Bool)]
[[1,2,3],[10],[76,9],[3]] :: [[Int]]
[’q’,’w’,’e’,’r’,’t’,’y’] :: [Char](= String)
“qwerty” :: [Char](= String)
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 10 / 13
The Empty List and the List Constructor
Recall from last week:
[] :: [a] (:) :: a -> [a] -> [a]
30:[] [30]
5:[10,20,30] [5, 10, 20, 30]
True:[True, False] [True, True, False]
’C’:[’u’,’s’,’e’] [’C’, ’u’,’s’,’e’] (= “Cuse”)
A key idea:
Every list matches exactly one of the following two patterns:
[] (the empty list)
(x:xs) (a nonempty list)
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 11 / 13
Pattern Matching on Lists: Two Very Common Patterns
[] is matched by an empty list.
(x:xs) is matched by any nonempty list:
the first element is bound to x, and the rest of list is bound to xs
Input x xs
[1,2,3] = 1:[2,3] 1 [2,3]
[True] = True:[] True []
[(5,’A’),(13,’g’)] = (5,’A’):[(13,’g’)] (5,’A’) [(13,’g’)]
[[1,2],[4],[8,9]] = [1,2]:[[4],[8,9]] [1,2] [[4],[8,9]]
What happens with the following patterns?
(x:y:zs) ((a,b):cs)
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 12 / 13
Examples of Pattern Matching
example1 :: (Int,Int) -> [Int]
example1 (3,x) = [x,1,x]
example1 (_,3) = []
example1 (w,y) = [w,y]
example2 :: (Int,Int) -> [Int]
example2 (w,y) = [w,y]
example2 (3,x) = [x,1,x]
example3 :: [Integer] -> (Char, Integer)
example3 (a:b:cs) = (’#’, b)
example3 _ = (’?’, 29)
example4 :: [(Char,Int)] -> Int
example4 [] = 0
example4 ((c,i):(d,e):rest) = e
example4 ((c,i):rest) = i*100
(CIS 252) Patterns, Tuples, and Lists 7 February 2017 13 / 13