8.3 Currying

Currying refers to converting an n-ary function into one that accepts only one argument and returns a function, which also accepts only one argument and returns a function that accepts only one argument, and so on. This technique was introduced by Moses Schönfinkel, although the term was coined by Christopher Strachey in 1967 and refers to logician Haskell Curry. For now, we can think of a curried function as one that permits transparent partial function application (i.e., without calling papply1 or papply). In other words, a curried function (or a function written in curried form, as discussed next) can be partially applied without calling papply1 or papply. Later, we see that a curried function is not being partially applied at all.

8.3.1 Curried Form

Consider the following two definitions of a power function (i.e., a function that computes a base b raised to an exponent e, b^e) in Haskell:

These definitions are almost the same. Notice that the definition of the powucf function has a comma between each parameter in the tuple of parameters, and that tuple is enclosed in parentheses; conversely, there are no commas and parentheses in the parameters tuple in the definition of the powcf function. As a result, the types of these functions are different.

The type of the powucf function states that it accepts a tuple of values of a type in the Num class and returns a value of a type in the Num class. In contrast, the type of the powcf function indicates that it accepts a value of a type in the Num class and returns a function mapping a value of a type in the Num class to a value of the same type in the Num class. The definition of powcf is written in curried form, meaning that it accepts only one argument and returns a function, also with only one argument:

By contrast, the definition of powucf is written in uncurried form, meaning that it must be invoked with arguments for all of its parameters with parentheses around the argument list and commas between individual arguments. In other words, powucf cannot be partially applied, without the use of papply1 or papply, but rather must be completely applied:

In these function applications, notice the absence of parentheses and commas when invoking the curried function and the presence of parentheses and commas when invoking the uncurried function. These syntactic differences are not stylistic; they are required. Parentheses and commas must not be included when invoking a curried function, while parentheses and commas must be included when invoking an uncurried function:

These examples bring us face-to-face with the fact that Haskell (and ML) perform literal pattern matching from function arguments to parameters (i.e., the parentheses and commas must also match).

8.3.2 Currying and Uncurrying

In general, currying transforms a function f_uncurried with the type signature

into a function f_curried with the type signature

such that

Currying f_uncurried and running the resulting f_curried function has the same effect as progressively partially applying f_uncurried. Inversely, uncurrying transforms a function f_curried with the type signature

into a function f_uncurried with the type signature

such that

8.3.3 The curry and uncurry Functions in Haskell

The built-in Haskell functions curry and uncurry are used to convert a binary function between uncurried and curried forms:

Currying and uncurrying are defined as higher-order functions (i.e., curry and uncurry, respectively) that each accept a function as an argument and return a function as a result (i.e., they are closed functions). In Haskell, the built-in function curry can accept only an uncurried binary function with type (a,b) -> c as input. Similarly, the built-in function uncurry can accept only a curried function with type a -> b -> c as input. The type signatures and λ-calculus for the functions curry and uncurry are given in Table 8.1. Definitions of curry and uncurry for binary functions in Haskell are given in Table 8.3. Notice that the definitions of curry and uncurry in Haskell are written in curried form. (Programming Exercises 8.3.22 and 8.3.23 involve defining curry and uncurry, respectively, in uncurried form in Haskell for binary functions.) Definitions of curry and uncurry for binary functions in Scheme are given in Table 8.4 and applied in the following examples:

Table 8.3 Definitions of curry and uncurry in Curried Form in Haskell for Binary Functions

Table 8.4 Definitions of curry and uncurry in Scheme for Binary Functions

A function that accepts only one argument is neither uncurried or curried. Therefore, we can only curry a function that accepts at least two arguments. User-defined and built-in functions in Haskell that accept only one argument can be invoked with or without parentheses around that single argument:

More generally, when a function is defined in curried form (or is curried), parentheses can be placed around any individual argument:

The functions papply1, papply, curry, and uncurry are closed: Each accepts a function as input and returns a function as output. It is necessary, but not sufficient, for a function to be closed to be able to be reapplied to its result. For instance, curry and uncurry are both closed, but neither can be reapplied to its own result. The functions papply1 and papply are closed, however, so each can be reapplied to its result as demonstrated previously.

8.3.4 Flexibility in Curried Functions

Technically, we do not and cannot partially apply a curried function because a curried function accepts only one argument. (This is why the functions papply1 and papply are not used.) Instead, we simply invoke a curried function in a manner conforming to its type, as with any other function. It just so happens that any curried function, and any function it returns, and any function which that function returns, and so on, accept only one argument. Therefore, with respect to its uncurried version, invoking a curried function appears to correspond to partially applying it, and partially applying its result, and so on. Consider the following definitions of a ternary addition function in uncurried and curried forms in Haskell:

While the function adducf can only be invoked one way [i.e., with the same number and types of arguments; e.g., adducf(1,2,3)], the function addcf can effectively be invoked in the following ways, including the one and only way the type of adducf specifies it must be invoked (i.e., with only one argument, as in the first invocation here):

Because the type of addcf is Num a => a -> a -> a -> a, we know it can accept only one argument. However, the second and third invocations of addcf just given make it appear as if it can accept two or three arguments as well. The absence of parentheses for precedence makes this illusion stronger. Let us consider the third invocation of addcf—that is, addcf 1 2 3. The addcf function is called as required with only one argument (addcf 1), which returns a new, unnamed function that is then implicitly invoked with one argument (<first returned proc> 2 or addcf’ 2), which returns another new, unnamed function, which is then implicitly invoked with one argument (<second returned proc> 3 or addcf” 3) and returns the sum 6. Using parentheses to make the implied precedence salient, the expression addcf 1 2 3 is evaluated as (((addcf 1) 2) 3):

Thus, even though a function written in curried form (e.g., addcf) can appear to be invoked with more than one argument (e.g., addcf 1 2 3), it can never accept more than one argument because the type of a curried function (or a function written in curried form) specifies that it must accept only one argument (e.g., Num a => a -> a -> a -> a).

The omission of superfluous parentheses for precedence in an invocation of a curried function must not be confused with the required absence of parentheses around the list of arguments:

Moreover, notice that in Haskell (and ML) an open parenthesis to the immediate right of the returned function is not required to force its implicit application, as is required in Scheme:

It is important to understand that the outermost parentheses around the Scheme expression ((papply (papply (papply add 1) 2) 3)) are needed to force the application of the returned function, and not for precedence.

A curried function is more flexible than its uncurried analog because it can effectively be invoked in n ways, where n is the number of arguments its uncurried analog accepts:

• the one and only way its uncurried analog is invoked (i.e., with all arguments as a complete application)

• the one and only way it itself can be invoked (i.e., with only one argument)

• n – 2 other ways corresponding to implicit partial applications of each returned function

More generally, if a curried function, whose uncurried analog accepts more than one parameter, is invoked with only arguments for a prefix of the parameters of its uncurried analog, it returns a new function accepting the arguments for the parameters of the uncurried analog whose arguments were left unsupplied; that new function, when invoked with arguments for those parameters, yields the same result as would have been returned had the original, uncurried function been invoked with arguments for all of its parameters. Thus, akin to partial function application, the invocation of a curried definition of a function f(p₁, p₂, ... , p_n) with arguments for a prefix of its parameters is

where m ≤ n, such that

Thus, any curried function can effectively be invoked with arguments for any prefix, including all of the parameters of its uncurried analog, without parentheses around the list of arguments or commas between individual arguments:

It might appear as if the complete application of an uncurried function is supported through its curried version, but it is not. Rather, the complete application is simulated, albeit transparently to the programmer, by a series of transparent, progressive partial function applications—one for the number of the parameters that the uncurried version of the function accepts—until a final result (i.e., an argumentless fixpoint function) is returned.

Given any uncurried, n-ary function f, currying supports—in a single function without calls to papply1 or papply—all n ways by which f can be partially applied and re-partially applied, and so on. For instance, given the ternary, uncurried Scheme function add, the function returned by the expression (curry add) supports the following three ways of partially and re-partially applying add:

In summary, any function accepting one or more arguments can be partially applied using papply1 and papply. Any curried function or any function written in curried form can be effectively partially applied without the use of the functions papply1 or papply. The advantage of partial function application is that it can be used with any function of any arity greater than zero even if the source code for the function to be partially applied is not available (e.g., in the case of a built-in function such as map in ML). The disadvantage of partial function application is that we must call the function papply1 or papply to partially apply a function, and this can get cumbersome and error prone, especially when re-partially applying the result of a partial application, and so on. The advantage of a curried function or a function written in curried form is that calls to papply1 or papply are unnecessary, so the effective partial function application is transparent. The disadvantage is that the function to be partially applied must be curried or written in curried form, and the function curry in Haskell only accepts a binary function. If we want to partially apply a function whose arity is greater than 2, we have two options. We can define it in curried form, which is not possible if its source code is unavailable. We can also define a version of curry that accepts a function with the same arity of the function we desire to curry. The latter approach is taken with the definition of curry in λ-calculus for a ternary function given in Table 8.1 and the definition of a function capable of currying a 4-ary function:

We can build general curry and uncurry functions that accept functions of any arity greater than 1, called implicit currying, through the use of Scheme macros, which we do not discuss here.

8.3.5 All Built-in Functions in Haskell Are Curried

All built-in Haskell functions are curried. This is why Haskell is referred to as a fully curried language. This is not the case in ML (Section 8.3.7 and Section 8.4). Built-in functions in Haskell that accept only one argument (e.g., even or odd) are neither uncurried nor curried and can be invoked with or without parentheses around their single argument:

Since all functions built into Haskell are curried, in online Appendix C we do not use parentheses around the argument tuples (or commas between individual arguments) when invoking built-in Haskell functions. For instance, consider our final definition of mergesort in Haskell given in online Appendix C:

Neither the mergesort function nor the compop function is curried. Thus, we cannot pass in the built-in < or > operators, because they are curried:

When passing an operator as an argument to a function, the passed operator must be a prefix operator. Since the operators < and > are infix operators, we cannot pass them to this version of mergesort without first converting them to prefix operators. We can convert an infix operator to a prefix operator either by wrapping it in a user-defined function or by enclosing it within parentheses:

This is why we wrapped these built-in, curried functions around uncurried, anonymous, user-defined functions when invoking mergesort:

However, we can use the uncurry function to simplify these invocations:

We cannot pass in one of the built-in, curried Haskell comparison operators [e.g., (<) or (>)] as is to mergesort without causing a type error:

For this version of mergesort to accept one of the built-in, curried Haskell comparison operators as a first argument, we must replace the subexpression compop(l, r) in line 21 of the definition of mergesort with (compop l r); that is, we must call compop without parentheses and a comma. This changes the type of mergesort from ((a, a) -> Bool, [a]) -> [a] to (a -> a -> Bool, [a]) -> [a]:

While this simple change causes the following invocations to work, we are mixing curried and uncurried functions. Specifically, the function mergesort is uncurried, while the function compop is curried:

Of course, now the following invocations no longer work, as expected:

Since all built-in Haskell functions are curried, we recommend consistently using only curried functions in a Haskell program. With a curried function we do not lose the ability to completely apply a function and we gain the flexibility and power that come with curried functions. Although uniformity is not required (i.e., it is akin to using consistent indentation to make a program more readable and reveal intended semantics), we recommend only using all curried functions or all uncurried functions in a Haskell (or ML) program. We recommend the former in Haskell since all built-in functions in Haskell are curried and since curried functions provide flexibility. Being consistent in using either all curried or all uncurried functions provides uniformity, helps avoid confusion, reduces program and type complexity, and reduces the scope for type errors. Following this guideline is challenging in ML because not all built-in functions are curried in ML; therefore, when defining functions in curried form in ML that call those uncurried built-in functions (e.g., Int.+ : int * int -> int or String.sub : string * int -> char), mixing the two forms is unavoidable.

The function mergesort is an ideal candidate for currying because by applying it in curried form with the < or > operators, we get back ascending-sort and descending-sort functions, respectively:

The following is the final, fully curried version of mergesort in curried form:

Using compop with mergesort demonstrates why in Haskell it is advantageous for purposes of uniformity to define all functions in curried form. That uniformity is a challenge to achieve in ML because not all built-in functions in ML are curried. For instance, the function Int.+ : int * int -> int is built into ML and uncurried, while the function map : (’a -> ’b) -> ’a list -> ’b list is built into ML and curried. Thus, defining a curried function that uses some built-in, uncurried ML functions leads to a mixture of curried and uncurried functions. In summary, four different types of mergesort are possible:

The first and last types are recommended (for purposes of uniformity) and the last type is preferred.

A consequence of all functions being fully curried in Haskell is that sometimes we must use parentheses to group syntactic entities. (We can think of this practice as forcing order or precedence, though that is not entirely true in Haskell; see Chapter 12.) For instance, in the expression isDigit (head "string"), the parentheses around head "string" are required to indicate that the entire argument to isDigit is head "string". Omitting these parentheses, as in isDigit head "string", causes the head function to be passed to the function isDigit, with the argument "string" then being passed to the result. In this case, enclosing the single argument head "string" in parentheses is not the same as enclosing the entire argument tuple in parentheses [i.e., isDigit (head "string") is not the same as isDigit('s')] because the former expression will generate an error without the parentheses and the latter does not. In other words, isDigit head ’string’ is incorrect and does not work while isDigit ’s’ is fine:

Moreover, and more importantly, curried functions open up new possibilities in programming, especially with respect to higher-order functions, as we will see in Section 8.4.

8.3.6 Supporting Curried Form Through First-Class Closures

Any language with first-class closures can be used to define functions in curried form. For instance, given that Haskell has first-class closures, even if Haskell did not have a syntax for curried form, we can define a function in curried form:

Defining functions in this manner weaves the curried form too tightly into the definition of the function and, as a result, makes the definition of the function cumbersome. Again, the main idea in these examples is that we can support the definition of functions in curried form in any language with first-class closures. For instance, because Python supports first-class closures, we can define the pow function in curried form in Python as well:

8.3.7 ML Analogs

Curried form is the same in ML as it is in Haskell:

Not all built-in ML functions are curried as in Haskell. For example, map is curried, while Int.+ is uncurried. Also, there are no built-in curry and uncurry functions in ML. User-defined and built-in functions in ML that accept only one argument, and which are neither uncurried or curried, can be invoked with or without parentheses around that single argument:

More generally, when a function is defined in curried form in ML, parentheses can be placed around any individual argument (as in Haskell):

Conceptual Exercises for Section 8.3

Exercise 8.3.1 Differentiate between between currying and curried form.

Exercise 8.3.2 Give one reason why you might want to curry a function.

Exercise 8.3.3 What is the motivation for currying?

Exercise 8.3.4 Consider the following function definition in Haskell:

This definition requires that the arguments for parameters b and c arrive together, as would happen when calling an uncurried function. Is f curried? Explain.

Exercise 8.3.5 Would the definition of curry in Haskell given in this section work as intended if curry was defined in uncurried form? Explain.

Exercise 8.3.6 Can a function f be defined in Haskell that returns a function with the same type as itself (i.e., as f)? If so, define f. If not, explain why not.

Exercise 8.3.7 In some languages, especially type-safe languages, including ML and Haskell, functions also have types, called type signatures. Consider the following three type signatures, which assume a binary function f : (a × b) → c.

Is curry = curry papply1? In other words, is curry returned if we pass the function papply1 to the function curry? Said differently, is curry self-generating? Explain why or why not, using type signatures to prove your case. Write a Haskell or ML program to prove why or why not.

Exercise 8.3.8 What might it mean to state that the curry operation acts as a virtual compiler (i.e., translator) to λ-calculus? Explain.

Exercise 8.3.9 We can sometimes factor out constant parameters from recursive function definitions so to avoid passing arguments that are not modified across multiple recursive calls (see Section 5.10.3 and Design Guideline 6: Factor Out Constant Parameters in Table 5.7).

(a) Does a recursive function with any constant parameters factored out execute more efficiently than one that is automatically generated using partial function application or currying to factor out those parameters?

(b) Which approach makes the function easier to define? Discuss trade-offs.

(c) Is the order of the parameters in the parameter list of the function definition relevant to each approach? Explain.

(d) Does the programming language used in each case raise any issues? Consider the language Scheme vis-à-vis the language Haskell.

Programming Exercises for Section 8.3

Return an anonymous function in each of the first four exercises.

Exercise 8.3.10 Define the function papply1 in curried form in Haskell for binary functions.

Exercise 8.3.11 Define the function papply1 in curried form in ML for binary functions.

Exercise 8.3.12 Define the function papply1 in uncurried form in Haskell for binary functions.

Exercise 8.3.13 Define the function papply1 in uncurried form in ML for binary functions.

Exercise 8.3.14 Define an ML function in curried form and then apply to its argument to create a new function. The function in curried form and the function resulting from applying it must be practical. For example, we could apply a sorting function parameterized on the list to be sorted and the type of items in the list or the comparison operator to be used, a root finding function parameterized by the degree and the number whose nth-root we desire, or a number converter parameterized by the base from which to be converted and the base to which to be converted.

Exercise 8.3.15 Complete Programming Exercise 8.3.14 in Haskell.

Exercise 8.3.16 Complete Programming Exercise 8.3.15, but this time define the function in uncurried form and then curry it using curry.

Exercise 8.3.17 Using higher-order functions and curried form, define a Haskell function dec2bin that converts a non-negative decimal integer to a list of zeros and ones representing the binary equivalent of that input integer.

Examples:

Exercise 8.3.18 Define an ML function map_ucf as a user-defined version of the built-in map function. The map_ucf function must be written in uncurried form and, therefore, is slightly different from the built-in ML map function. Explain this difference in a program comment.

Exercise 8.3.19 Define the pow function from this section in Scheme so that it can be partially applied without the use of the functions papply1, papply, or curry. The pow function must have the type integer → integer → integer. Then use that definition to define the functions square and cube. Do not define any other named function or any named, nested function other than pow.

Exercise 8.3.20 Define the function curry in curried form in ML for binary functions. Do not return an anonymous function.

Exercise 8.3.21 Define the function uncurry in curried form in ML for binary functions. Do not return an anonymous function.

Return an anonymous function in each of the following six exercises.

Exercise 8.3.22 Define the function curry in uncurried form in Haskell for binary functions.

Exercise 8.3.23 Define the function uncurry in uncurried form in Haskell for binary functions.

Exercise 8.3.24 Define the function curry in uncurried form in ML for binary functions.

Exercise 8.3.25 Define the function uncurry in uncurried form in ML for binary functions.

Exercise 8.3.26 Define the function curry in Python for binary functions.

Exercise 8.3.27 Define the function uncurry in Python for binary functions.