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 + 18The conditional equation above represents a (very large!) collectionof mathematical relationships:tame 10 7 = simple 10 (7+2)tame 5 200 = 200 + 18tame (-2) 4 = simple (-2) (4 + 2)tame 300 5 = simple 300 (5+2)…(CIS 252) Scope, Lists, and Recursion 31 January 2017 3 / 12Scope: Which Name is Which?Consider the following code:x, y :: Intx = 10y = 12thrice :: 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)wherefeet = fromInteger (floor (meas / 12))inches = meas – 12*feet(CIS 252) Scope, Lists, and Recursion 31 January 2017 7 / 12Introducing: ListsList TypesSuppose t is a type. Then [t] is a type.[Bool] [Int] [Float] [Integer] [Char] [[Bool]][[Int]] [[Float]]List ValuesThe 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 / 12The 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 / 12Building 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) itemThis code represents a collection of mathematical relationships:series (-2) False = []series (-1) False = []series 0 False = []series 1 False = False : series 0 Falseseries 2 False = False : series 1 Falseseries 3 False = False : series 2 False…(CIS 252) Scope, Lists, and Recursion 31 January 2017 11 / 12Recursion: Simple Idea, Powerful TechniqueDefinitionRecursion is the process of defining a mathematical object (such as a setor 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 itemPlace 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
Reviews
There are no reviews yet.