What do you get when you curry partial application?

Currying and partial application are very similar, in fact so similar that lots of people get them confused.

Currying is a unary function, meaning it takes only one argument. That argument is a function and the curry returns another function. The only difference between the two functions is how the arguments are applied. Because nearly every Haskell function is already curried it's going to be easier to see this in C++.

int add( int a, int b ) { return a + b };
int ten = add( 7, 3 ); // Normal uncurried form
int eleven = curry( add )( 7 )( 4 ); // Curried form

The difference between the curried and uncurried forms is that normally we apply the arguments together, but once curried we apply the arguments one after another.

Partial application is a binary function. It takes a function and an argument and it also returns a function.

int add( int a, int b ) { return a + b };
int ten = add( 7, 3 ); // Normal form
int eleven = papply( add, 7 )( 4 ); // Partial application

You can see this is very similar to currying. Partial application is very easy to write in C++ using the Boost.Lambda or Boost.Bind libraries — I'm going to use Boost.Lambda.

template< typename R, typename V1, typename V2 >
boost::function< R ( V2 ) > papply( boost::function< R ( V1, V2 ) > f, V1 v ) {
    return boost::lambda::bind( f, v, boost::lambda::_1 );
}

Given this it is fairly easy to write a curry function:

template< typename R, typename V1, typename V2 >
boost::function< boost::function< R ( V1 ) > ( V2 ) > curry( boost::function< R ( V1, V2 ) > f ) {
    return boost::lambda::bind( papply< R, V1, V2 >, f, boost::lambda::_1 );
}

What I wanted to know was what the result of currying papply would be? Thinking it through I was expecting some form of curry to be the result. It turns out I was wrong.

let papply ( f, a ) b = f ( a, b )

let curry f ( a, b ) = papply ( f, a ) b

Prelude> inc 8
9
Prelude> inc 10
11
Prelude> inc 2324
2325

Haskell is good for trying this sort of thing, but it isn't entirely straightforward. Although the error messages are shorter (much shorter) they're not really any more illuminating. Another complication is that in Haskell it is normal to write all functions in curried form. Trying to write these function in uncurried form took me quite some time, in fact much longer than it took me to write them in C++. In any case I ended up with this for partial application:

papply ( f, a ) b = f ( a, b )

Following the way that the C++ curry is defined, the same thing in Haskell becomes this:

curry f ( a, b ) = papply ( f, a ) b

We need a function to practice on so we can convince ourselves that we're doing sensible things. Turning addition into an increment function seems a perfectly likely candidate. Here are two different versions. If you can understand the second you probably don't need to be reading this post (I'm going to assume you're doing this in GHCi—see the sidebar).

let add ( a, b ) = a + b
let add = uncurry (+)

Whichever definition of add you want to use, increment is the same:

let inc = papply ( add, 1 )

One useful thing that GHCi can do is to tell you the type of an expression. We do this by typing :t before the expression:

Prelude> :t papply
papply :: ((t, t1) -> t2, t) -> t1 -> t2
Prelude> :t curry
curry :: ((t, t1) -> t2) -> (t, t1) -> t2

I don't want to go into what those type signatures mean, but we do now have enough to answer the question, what is the result of currying partial application?

Prelude> :t curry papply
curry papply :: ((t, t1) -> t2, t) -> t1 -> t2

Look carefully and this is the same type signature as partial application, not curry as I was expecting. We show that it does work as partial application with this:

let inc = ( curry papply ) ( add, 1 )

Try using that and you should be able to convince yourself that it works. We can curry that result as often as we like and it will still work:

let inc = ( curry $ curry papply ) ( add, 1 )
let inc = ( curry $ curry $ curry papply ) ( add, 1 )

Now I just hope that somebody can explain, in terms simple enough even for me to understand, why this happens.

Why does currying this particular binary function give back a binary function? I think that I have something wrong because I can't apply my Haskell insight back into C++. The following C++ fails to compile for me:

#include <boost/function.hpp>
#include <boost/lambda/bind.hpp>
#include <cmath>
#include <iostream>


template< typename R, typename V1, typename V2 >
boost::function< R ( V2 ) > papply( boost::function< R ( V1, V2 ) > f, V1 v ) {
    return boost::lambda::bind( f, v, boost::lambda::_1 );
}
template< typename R, typename V1, typename V2 >
boost::function< boost::function< R ( V1 ) > ( V2 ) > curry( boost::function< R ( V1, V2 ) > f ) {
    return boost::lambda::bind( papply< R, V1, V2 >, f, boost::lambda::_1 );
}

int add( int a, int b ) { return a + b; }

int main() {
	// Explicitly making these functors makes things a bit simpler
	boost::function< int ( int, int ) > fadd( add );
	boost::function< boost::function< int ( int ) > ( boost::function< int ( int, int ) >, int ) > fpapply( papply< int, int, int > );

	boost::function< int ( int ) > inc1( papply( fadd, 1 ) );
	std::cout << inc1( 6 ) << " " << inc1( 10 ) << std::endl;

	boost::function< int ( int ) > inc2( fpapply( fadd, 1 ) );	
	std::cout << inc2( 6 ) << " " << inc2( 10 ) << std::endl;

	curry( fpapply ); // Fails with a very nasty error nearly 180 lines long
}

If the Haskell is correct I think I should be able to define inc3 as:

boost::function< int ( int ) > inc3( curry( fpapply )( fadd, 1 ) )

Although what I was expecting was this:

boost::function< int ( int ) > inc3( curry( fpapply )( fadd )( 1 ) )

In either case I can't get past the first hurdle because curry( fpapply ) won't compile, but I've probably got a stupid bug somewhere.