[SOLVED] 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 thats 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 (dont 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 functions 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

Whats 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 dont deconstruct data.

Weve 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