kuniga.me > NP-Incompleteness > Haskell – Function Currying

06 Nov 2011

Function currying corresponds to the partial evaluation of a function’s arguments. The technique is named after Haskell Curry, who according to Wikipedia [1] re-invented the method (Moses Schönfinkel had already developed the method previously). The Haskell language is also named after Curry.

In this post I will talk a little about currying functions in Haskell, based mainly on Chapter 4 of the book Real World Haskell [1].

## Functions with multiple arguments in Haskell

The syntax for specifying the type of a function in Haskell with multiple arguments seems a bit confusing at first. For example, if we want to define a function that sums two integers, we must specify it as follows.

From the header it doesn’t give the impression that the function takes two integers as an argument and returns an integer. That’s because functions in Haskell actually take only one argument. When there are multiple arguments, we call the f function with the first argument and return a g function with the occurrences of that first argument replaced by the value passed as the argument.

For example, consider a function f(a, b, c) over three integers a, b and c. The first call of the function f(1,2,3) returns a new function g(b, c) = f(1, b, c), which in turn returns another function h(c) = g(2, c), which takes only one argument.

To test this in practice, we can do in the terminal (ghci):

In the example above, the parameter a of sum, was replaced by 3 and the resulting function assigned to sumThree, which now only takes one argument.

In a function with several parameters, we can work with intermediate functions resulting from the currying process by providing only some of the parameters. For example,

In this case, foo1 receives two arguments, foo2 just one and foo3 is already the result of the function foo.

## Skipping parameters using currying

Suppose we want to select prime numbers from an input list. A very simple version, where we try to find a divisor of p going from 2 to $sqrt{p}$, can be given by:

In Haskell’s standard library, there is a function called filter, which takes an array and a predicate (i.e. function that takes an element of that array and returns true or false). We can pass our function isPrime to generate a list with prime elements from 1 to 50 for example.

To make it easier, we can create a function that receives an array and returns the list of primes:

Using currying, it is possible to define the function above without parameter

In the first case, we are basically defining a new wrapper function that will call filter isPrime when invoked. In the second, we are more or less creating an alias to filter isPrime.

## Currying over the second parameter

By default, the substitution of arguments is done from the first argument, that is, from left to right. However, for functions with two (binary) parameters, we can use infix notation to replace the second argument first.

The infix notation consists of calling the function between(backticksbacktick). For example, the sum function could be called like this:

This syntax is interesting for code readability purposes. When calling the function in infix form passing only the second argument, the substitution is done only for it. As an example, let’s define the power function that takes two integers a and b and raises a to b (the sum function isn’t funny because it’s commutative).

Now we can curry and apply the function to just one argument

## Currying in C++

The STL provides some tools for working with the functional paradigm, through the library functional. Through it we can reproduce our first example in Haskell:

In this case we work with a functor, which is an object representing a function. The class adder must derive from the class binary_function. The function bind1st makes a bind of the first argument of the function, and returns an object of type binder1st, which derives from the class unary_function which takes a single argument.

It is possible to bind the second argument using the function bind2nd.

## References

• [1] Real World Haskell - Chapter 4, by Bryan O’Sullivan, Don Stewart, and John Goerzen.