Topic Pot Pourri: Scope, Lists, and Recursion
Topic Pot Pourri: Scope, Lists, and Recursion
Prof. Susan Older
31 January 2017
(CIS 252) Scope, Lists, and Recursion 31 January 2017 1 / 12
Another Look at Function Definitions
Consider the following definition:
simple :: Int -> Int -> Int
simple a b = a + 3*b
The formal parameters a and b are names used as placeholders for
input values that may be passed into the function.
The single equation above represents a (very large!) collection of
mathematical relationships:
simple 10 7 = 10 + 3*7
simple 5 200 = 5 + 3*200
simple (-2) 4 = -2 + 3*4
simple 30 500 = 30 + 3*500
…
(CIS 252) Scope, Lists, and Recursion 31 January 2017 2 / 12
Another Look at Conditional Equations
Consider the following definition:
tame :: Int -> Int -> Int
tame a b
| b < 10 = simple a (b+2) | otherwise = b + 18 The conditional equation above represents a (very large!) collection of mathematical relationships: tame 10 7 = simple 10 (7+2) tame 5 200 = 200 + 18 tame (-2) 4 = simple (-2) (4 + 2) tame 300 5 = simple 300 (5+2) ... (CIS 252) Scope, Lists, and Recursion 31 January 2017 3 / 12 Scope: Which Name is Which? Consider the following code: x, y :: Int x = 10 y = 12 thrice :: Int -> Int
thrice x = 3*x
simple :: Int -> Int
simple x = x + y
extra :: Int -> Bool
extra y = x > y
There are eight definitions of names:
Five top-level definitions: x, y,
thrice, simple, extra.
Two definitions of name x as a
formal parameter: see thrice and
simple
One definition of name y as a
formal parameter: see extra
What is a definition’s scope?
The portion of the code where references
to that name refer to that specific
definition.
(CIS 252) Scope, Lists, and Recursion 31 January 2017 4 / 12
Scope in Haskell: How Does it Work?
Consider the following code:
x, y :: Int
x = 10
y = 12
thrice :: Int -> Int
thrice x = 3*x
simple :: Int -> Int
simple x = x + y
extra :: Int -> Bool
extra y = x > y
The formal parameter x in thrice:
Has as its scope the body of thrice
“Cuts a hole in the scope” of the
top-level definition of x
The formal parameter y in extra:
Has as its scope the body of extra
“Cuts a hole in the scope” of the
top-level definition of y
Top-level definitions have the entire
program (minus any holes cut by inner
declarations) as their scope
(CIS 252) Scope, Lists, and Recursion 31 January 2017 5 / 12
Local Variables in Haskell
Local variables are visible only inside a definition:
maxSq :: Int -> Int -> Int
maxSq x y
| sq x > sq y = sq x
| otherwise = sq y
where
sq :: Int -> Int
sq w = w*w
maxSq’ :: Int -> Int -> Int
maxSq’ x y
| sqx > sqy = sqx
| otherwise = sqy
where
sqx = x*x
sqy = y*y
The ramifications:
sq is visible/usable only within definition of maxSq
sqx and sqy are visible/usable only within definition of maxSq’
(CIS 252) Scope, Lists, and Recursion 31 January 2017 6 / 12
Local Variables: Reasons to Use Them
Enhance the legibility of your code, especially when the same
calculation is performed multiple times
Control access to a helper function
Clean up your name space
An example of their use:
— convert a measurement in inches to feet-and-inches
convert :: Float -> (Float, Float)
convert meas
| meas <0 = (0,0) -- avoid negative measures | otherwise = (feet, inches) where feet = fromInteger (floor (meas / 12)) inches = meas - 12*feet (CIS 252) Scope, Lists, and Recursion 31 January 2017 7 / 12 Introducing: Lists List Types Suppose t is a type. Then [t] is a type. [Bool] [Int] [Float] [Integer] [Char] [[Bool]] [[Int]] [[Float]] List Values The values of type [t] are lists whose elements all have type t. [True,False,False,True,False] :: [Bool] [5,10,15,24] :: [Int] [6.318, -2.5, 100.079] :: [Float] [[1,2,3],[10],[76,9],[3]] :: [[Int]] [’q’,’w’,’e’,’r’,’t’,’y’] :: [Char](= String) "qwerty" :: [Char](= String) (CIS 252) Scope, Lists, and Recursion 31 January 2017 8 / 12 The Simplest List is the Empty List: [] The empty list [ ] contains no elements. What is the type of [ ]? [ ] is polymorphic (Greek for “many shapes”): [ ] :: [a] In this usage, a is a type variable. Any valid type can be plugged in for a: [ ] :: [Bool] [ ] :: [Int] [ ] :: [Float] [ ] :: [[Bool]] ... (CIS 252) Scope, Lists, and Recursion 31 January 2017 9 / 12 Building up Lists: The List Constructor : is pronounced “cons”: (:) :: 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”)
1:2:3:[] [1, 2, 3] (cons is right-associative)
17:[True, False] Type error!
(CIS 252) Scope, Lists, and Recursion 31 January 2017 10 / 12
Coming Full Circle: What Does This Function Do?
Consider the following code:
series :: Int -> a -> [a]
series n item
| n <= 0 = [] | otherwise = item : series (n-1) item This code represents a collection of mathematical relationships: series (-2) False = [] series (-1) False = [] series 0 False = [] series 1 False = False : series 0 False series 2 False = False : series 1 False series 3 False = False : series 2 False ... (CIS 252) Scope, Lists, and Recursion 31 January 2017 11 / 12 Recursion: Simple Idea, Powerful Technique Definition Recursion is the process of defining a mathematical object (such as a set or a function) in terms of itself. How do you generate a list containing n copies of item? If n is zero (or negative), return the empty list. If n is positive, then: Generate a list with n-1 copies of item Place an extra copy of item on the front of the list. series :: Int -> a -> [a]
series n item
| n <= 0 = [] | otherwise = item : series (n-1) item (CIS 252) Scope, Lists, and Recursion 31 January 2017 12 / 12