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 functionnr“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