[SOLVED] Haskell Topic Pot Pourri: Scope, Lists, and Recursion

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 definitions 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