# 程序代写代做代考 Patterns and Tuples and Lists (Oh, My!)

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