Created 9th September, 2007 16:29 (UTC), last edited 6th October, 2007 06:04 (UTC)

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.

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.

© 2002-2019 Kirit & Tai Sælensminde. All forum posts are copyright their respective authors.

Licensed under a Creative Commons License. Non-commercial use is fine so long as you provide attribution.

kirit.com