DOC PREVIEW
UA CSC 520 - Declaring Infix Functions

This preview shows page 1-2-3 out of 8 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 8 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 8 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 8 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 8 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSc 520Principles of Programming Languages15: Haskell — Curried FunctionsChristian CollbergDepartment of Computer ScienceUniversity of [email protected] 2005 Christian CollbergApril 22, 20051 Declaring Infix Functions• Sometimes it is more natural to use an infix notation for a function application, rather than the normalprefix one:– 5 + 6 (infix)– (+) 5 6 (prefix)• Haskell predeclares some infix operators in the standard prelude, such as those for arithmetic.• For each operator we need to specify its precedence and associativity. The higher precedence of anoperator, the stronger it binds (attracts) its arguments: hence:3 + 5*4 ≡ 3 + (5*4)3 + 5*4 6≡ (3 + 5) * 42 Declaring Infix Functions. . .• The associativity of an operator describes how it binds when combined with operators of equal prece-dence. So, is5-3+9 ≡ (5-3)+9 = 11OR5-3+9 ≡ 5-(3+9) = -7The answer is that + and - associate to the left, i.e. parentheses are inserted from the left.• Some operators are right associative: 5^3^2 ≡ 5^(3^2)• Some operators have free (or no) associativity. Combining operators with free associativity is an error:5 == 4 < 3 ⇒ ERROR13 Declaring Infix Functions. . .• The syntax for declaring operators:infixr prec oper -- right assoc.infixl prec oper -- left assoc.infix prec oper -- free assoc.From the standard prelude:infixl 7 *infix 7 /, ‘div‘, ‘rem‘, ‘mod‘infix 4 ==, /=, <, <=, >=, >• An infix function can be used in a prefix function application, by including it in parenthesis. Example:? (+) 5 ((*) 6 4)294 Multi-Argument Functions• Haskell only supports one-argument functions.• An n-argument function f (a1, · · · , an) is constructed in either of two ways:1. By making the one input argument to f atuple holding the n arguments.2. By letting f “consume” one argument at a time. This is called currying.Tuple Curryingadd :: (Int,Int)->Intadd (a, b) = a + badd :: Int->Int->Intadd a b = a + b5 Currying• Currying is the preferred way of constructing multi-argument functions.• The main advantage of currying is that it allows us to define specialized versions of an existing function.• A function is specialized by supplying values for one or more (but not all) of its arguments.• Let’s look at Haskell’s plus operator (+). It has the type(+) :: Int -> (Int -> Int).• If we give two arguments to (+) it will return an Int:(+) 5 3 ⇒ 826 Currying. . .• If we just give one argument (5) to (+) it will instead return a function which “adds 5 to things”. Thetype of this specialized version of (+) is Int -> Int.• Internally, Haskell constructs an intermediate – specialized – function:add5 :: Int -> Intadd5 a = 5 + a• Hence,(+) 5 3 is evaluated in two steps. First (+) 5 is evaluated. It returns a function which adds5 to its argument. We apply the second argument 3 to this new function, and the result 8 is returned.7 Currying. . .• To summarize, Haskell only supports one-argument functions. Multi-argument functions are con-structed by successive application of arguments, one at a time.• Currying is named after logician Haskell B. Curry (1900-1982) who popularized it. It was invented bySch¨onfinkel in 1924. Sch¨onfinkeling doesn’t sound too good...• Note: Function application (f x) has higher precedence (10) than any other operator. Example:f 5 + 1 ⇔ (f 5) + 1f 5 6 ⇔ (f 5) 68 Currying Example• Let’s see what happens when we evaluate f 3 4 5, where f is a 3-argument function that returns thesum of its arguments.f :: Int -> (Int -> (Int -> Int))f x y z = x + y + zf 3 4 5 ≡ ((f 3) 4) 59 Currying Example. . .• (f 3) returns a function f’ y z (f’ is a specialization of f) that adds 3 to its next two arguments.f 3 4 5 ≡ ((f 3) 4) 5 ⇒ (f’ 4) 5f’ :: Int -> (Int -> Int)f’ y z = 3 + y + z10 Currying Example. . .• (f’ 4) (≡ (f 3) 4) returns a function f’’z (f’’ is a specialization of f’) that adds (3+4) to itsargument.3f 3 4 5 ≡ ((f 3) 4) 5 ⇒ (f’ 4) 5⇒ f’’ 5f’’ :: Int -> Intf’’ z = 3 + 4 + z• Finally, we can apply f’’ to the last argument (5) and get the result:f 3 4 5 ≡ ((f 3) 4) 5 ⇒ (f’ 4) 5⇒ f’’ 5 ⇒ 3+4+5 ⇒ 1211 Currying ExampleThe Combinatorial Function:• The combinatorial functionnr“n choose r”, computes the number of ways to pick r objects from n.nr=n!r! ∗ (n − r)!In Haskell:comb :: Int -> Int -> Intcomb n r = fact n/(fact r*fact(n-r))? comb 5 31012 Currying Example. . .comb :: Int -> Int -> Intcomb n r = fact n/(fact r*fact(n-r))comb 5 3 ⇒ (comb 5) 3 ⇒comb53 ⇒120 / (fact 3 * (fact 5-3)) ⇒120 / (6 * (fact 5-3)) ⇒120 / (6 * fact 2) ⇒120 / (6 * 2) ⇒120 / 12 ⇒10comb5r = 120 / (fact r * fact(5-r))• comb5is the result of partially applying comb to its first argument.13 Associativity• Function application is left-associative:f a b = (f a) b f a b 6= f (a b)• The function space symbol ‘->’ is right-associative:4a -> b -> c = a -> (b -> c)a -> b -> c 6= (a -> b) -> c• f takes an Int as argument and returns a function of type Int -> Int. g takes a function of type Int-> Int as argument and returns an Int:f’ :: Int -> (Int -> Int)mf :: Int -> Int -> Int6mg :: (Int -> Int) -> Int14 What’s the Type, Mr. Wolf?• If the type of a function f ist1-> t2-> · · · -> tn-> t• and f is applied to argumentse1::t1, e2::t2, · · ·, ek::tk,• and k ≤ n• then the result type is given by cancelling the types t1· · · tk:6 t1-> 6 t2-> · · · -> 6 tk-> tk+1-> · · · -> tn-> t• Hence,f e1e2· · · ekreturns an object of typetk+1-> · · · -> tn-> t.• This is called the Rule of Cancellation.15 Polymorphic Functions• In Pascal we can’t write a generic sort routine, i.e. one that can sort arrays of integers as well as arraysof reals:procedure Sort (var A : array of <type>;n : integer);• In Haskell (and many other FP languages) we can write polymorphic (“many shapes”) functions.• Functions of polymorphic type are defined by using type variables in the signature:length :: [a] -> Intlength s = ...516 Polymorphic Functions. . .• length is a function from lists of elements of some (unspecified) type a, to integer. I.e. it doesn’tmatter if we’re taking the length of a list of integers or a list of reals or strings, the algorithm is thesame.length [1,2,3] ⇒ 3 (list of Int)length ["Hi ", "there", "!"] ⇒ 3 (list of String)length "Hi!" ⇒ 3 (list of Char)17


View Full Document

UA CSC 520 - Declaring Infix Functions

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 Declaring Infix Functions
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 Declaring Infix Functions 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 Declaring Infix Functions 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?