DOC PREVIEW
UA CSC 520 - Function Definitions

This preview shows page 1-2-3-4-5-6 out of 18 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 18 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Defining FunctionsDefining Functionsldots Defining Functionsldots Defining Functionsldots Standard Recursive FunctionsSimulating Recursive FunctionsTree View of { t fact 3}Tree View of { t fact 3}Box View of { t fact 3}Box View of { t fact 3}ldots Box View of { t fact 3}ldots Reduction View of { t fact 3}Reduction View of { t fact 3}ldots Recursion Over ListsThe { t length} FunctionReduction View of { t len [5,6]}Tree View of { t len [5,6,7]}520—Spring 2005—12CSc 520Principles of ProgrammingLanguages12: Haskell — Function DefinitionsChristian [email protected] of Computer ScienceUniversity of ArizonaCopyrightc 2005 Christian Collberg[1]520—Spring 2005—12Defining FunctionsWhen programming in a functional language we havebasically two techniques to choose from when defininga new function:1. Recursion2. CompositionRecursion is often used for basic “low-level” functions,such that might be defined in a function library.Composition (which we will cover later) is used tocombine such basic functions into more powerful ones.Recursion is closely related to proof by induction.[2]520—Spring 2005—12Defining Functions...Here’s the ubiquitous factorial function:fact :: Int -> Intfact n = if n == 0 then1elsen * fact (n-1)The first part of a function definition is the typesignature, which gives the domain and range of thefunction:fact :: Int -> IntThe second part of the definition is the functiondeclaration, the implementation of the function:fact n = if n == 0 then · · ·[3]520—Spring 2005—12Defining Functions...The syntax of a type signature isfun name :: argument typesfacttakes one integer input argument and returns oneinteger result.The syntax of function declarations:fun name param names = fun bodyif e1then e2else e3is a conditional expressionthat returns the value of e2if e1evaluates to True. If e1evaluates to False, then the value of e3is returned.Examples:if False then 5 else 6 ⇒ 6if 1==2 then 5 else 6 ⇒ 65 + if 1==1 then 3 else 2 ⇒ 8[4]520—Spring 2005—12Defining Functions...fact is defined recursively, i.e. the function bodycontains an application of the function itself.The syntax of function application is: fun name arg.This syntax is known as “juxtaposition”.We will discuss multi-argument functions later. For now,this is what a multi-argument function application (“call”)looks like:fun name arg 1 arg 2 · · · arg nFunction application examples:fact 1 ⇒ 1fact 5 ⇒ 120fact (3+2) ⇒ 120[5]520—Spring 2005—12Standard Recursive FunctionsTypically, a recursive function definition consists of aguard (a boolean expression), a base case (evaluatedwhen the guard isTrue), and a general case(evaluated when the guard is False).fact n =if n == 0 then ⇐ guard1 ⇐ base caseelsen * fact (n-1) ⇐ general case[6]520—Spring 2005—12Simulating Recursive FunctionsWe can visualize the evaluation of fact 3 using a treeview, box view, or reduction view.The tree and box views emphasize the flow-of-controlfrom one level of recursion to the nextThe reduction view emphasizes the substitution stepsthat the hugs interpreter goes through when evaluatinga function. In our notation boxed subexpressions aresubstituted or evaluated in the next reduction.Note that the Haskell interpreter may not go throughexactly the same steps as shown in our simulations.More about this later.[7]520—Spring 2005—12Tree View of fact 3if 2==0 then 1else 2 * fact (2−1)if 1==0 then 1else 1 * fact (1−1)if 0==0 then 1else ...if 3==0 then 1else 3 * fact (3−1)fact 2fact 1fact 0fact 3This is a Tree View offact 3.We keep goingdeeper into the recur-sion (evaluating thegeneral case) until theguard is evaluated toTrue.[8]520—Spring 2005—12Tree View of fact 3if 2==0 then 1else 2 * fact (2−1)if 1==0 then 1else 1 * fact (1−1)if 0==0 then 1else ...if 3==0 then 1else 3 * fact (3−1)fact 2fact 1fact 013*2=62*1=21*1=1fact 3When the guard isTrue we evaluate thebase case and returnback up through thelayers of recursion.[9]520—Spring 2005—12Box View of fact 33fact 3False2fact 2ifthenelse==10−1*[10]520—Spring 2005—12Box View of fact 3...False1fact 1ifthenelse==10−1*fact 3False2==10−ifthenelse1*fact 23[11]520—Spring 2005—12Box View of fact 3...fact 3False2==10−ifthenelse1*fact 2False1fact 1ifthenelse==10−1*−3[12]520—Spring 2005—12Reduction View of fact 3fact 3 ⇒if 3 == 0 then 1 else 3 * fact (3-1) ⇒if False then 1 else 3 * fact (3-1) ⇒3 * fact (3-1) ⇒3 * fact 2 ⇒3 * if 2 == 0 then 1 else 2 * fact (2-1)⇒3 * if False then 1 else 2 * fact (2-1) ⇒3 * (2 * fact (2-1)) ⇒3 * (2 * fact 1) ⇒3 * (2 * if 1 == 0 then 1 else 1 * fact (1-1))⇒ · · ·[13]520—Spring 2005—12Reduction View of fact 3...3 * (2 * if 1 == 0 then 1 else 1 * fact (1-1)) ⇒3 * (2 * if False then 1 else 1 * fact (1-1)) ⇒3 * (2 * (1 * fact (1-1))) ⇒3 * (2 * (1 * fact 0)) ⇒3 * (2 * (1 * if 0 == 0 then 1 else 0 * fact (0-1))) ⇒3 * (2 * (1 * if True then 1 else 0 * fact (0-1))) ⇒3 * (2 * (1 * 1)) ⇒3 * (2 * 1) ⇒3 * 2 ⇒6[14]520—Spring 2005—12Recursion Over ListsIn the fact function the guard was n==0, and therecursive step was fact(n-1). I.e. we subtracted 1from fact’s argument to make a simpler (smaller)recursive case.We can do something similar to recurse over a list:1. The guard will often be n==[ ] (other tests are ofcourse possible).2. To get a smaller list to recurse over, we often split thelist into its head and tail,head:tail.3. The recursive function application will often be onthe tail,f tail.[15]520—Spring 2005—12The length FunctionIn English:The length of the empty list [ ] is zero. The lengthof a non-empty listS is one plus the length of thetail ofS.In Haskell:len :: [Int] -> Intlen s = if s == [ ] then0else1 + len (tail s)We first check if we’ve reached the end of the list s==[]. Otherwise we compute the length of the tail of s, andadd one to get the length ofs itself.[16]520—Spring 2005—12Reduction View of len [5,6]len s = if s == [ ] then 0 else 1 + len (tail s)len [5,6] ⇒if [5,6]==[ ] then 0 else 1 + len (tail [5,6]) ⇒1 + len (tail [5,6]) ⇒1 + len [6] ⇒1 + (if [6]==[ ] then 0 else 1 + len (tail [6])) ⇒1 + (1 + len (tail [6])) ⇒1 + (1 + len [ ]) ⇒1 + (1 + (if [ ]==[ ] then 0 else 1+len (tail [ ]))) ⇒1 + (1 + 0)) ⇒ 1 + 1 ⇒ 2[17]520—Spring 2005—12Tree View of len [5,6,7]len [6,7]len [7]len []1+2=31+0=1len [5,6,7]if [5,6,7]==[] then 0if [6,7]==[] then 0if [7]==[] then 0if []==[] then


View Full Document

UA CSC 520 - Function Definitions

Documents in this Course
Handout

Handout

13 pages

Semantics

Semantics

15 pages

Haskell

Haskell

15 pages

Recursion

Recursion

18 pages

Semantics

Semantics

12 pages

Scheme

Scheme

32 pages

Syllabus

Syllabus

40 pages

Haskell

Haskell

17 pages

Scheme

Scheme

27 pages

Scheme

Scheme

9 pages

TypeS

TypeS

13 pages

Scheme

Scheme

27 pages

Syllabus

Syllabus

10 pages

Types

Types

16 pages

FORTRAN

FORTRAN

10 pages

Load more
Download Function Definitions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Function Definitions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Function Definitions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?