www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - A currying function

reply "bearophile" <bearophileHUGS lycos.com> writes:
I think std.functional.curry is badly named because I think it's 
a "partial application" (I suggest to rename it).


In Haskell and Scala currying is built-in, this is Haskell, shell 
(ghci):

Prelude> let foo x y z = x * 2 + y * 3 + y * 5
Prelude> let foo1 = foo 5
Prelude> let foo2 = foo1 4
Prelude> foo2 3
42


Through Reddit I've found a curry() in C++11:
https://github.com/LeszekSwirski/cpp-curry


So I've written a D version of it below, not tested much. I have 
not translated the C++11 version. This was quite easy to write, 
and much simpler and shorter than the C++11 version (but maybe 
this misses something, this is just a first draft). This kind of 
stuff was quite longer to do in D1, but now with CTFE on strings 
ops, defining one or more inner static functions that build a 
string at compile-time, it's quite easy. Now I don't need lot of 
templates to do this.

There are two alternative designs, curry1 seems a bit more 
elegant, but if you want to use it in-place it forces you to add 
a () at the beginning, that's not nice and intuitive. So probably 
curry2 is better.


import std.traits: isCallable, ParameterTypeTuple;
import std.string: join;
import std.conv: xformat;

 property curry1(alias F)() if (isCallable!F) {
     static string genChain() {
         string[] chain;
         string[] args;
         foreach (i, T; ParameterTypeTuple!F) {
             chain ~= xformat("(%s x%d)", T.stringof, i);
             args ~= xformat("x%d", i);
         }
         return chain.join(" => ") ~ " => F(" ~ args.join(", ") ~ 
");";
     }
     mixin("return " ~ genChain());
}

auto curry2(F)(F f) if (isCallable!F) {
     static string genChain() {
         string[] chain;
         string[] args;
         foreach (i, T; ParameterTypeTuple!F) {
             chain ~= xformat("(%s x%d)", T.stringof, i);
             args ~= xformat("x%d", i);
         }
         return chain.join(" => ") ~ " => f(" ~ args.join(", ") ~ 
");";
     }
     mixin("return " ~ genChain());
}

// default arguments are ignored
double foo(immutable int x, in float y, short z=5) pure nothrow {
     return x * 2 + y * 3 + y * 5;
}

void main() {
     import std.stdio;

     writeln(foo(5, 4, 3));

     auto cf = curry1!foo;
     auto c2 = cf(5)(4);
     writeln(c2(3));

     writeln(curry1!foo()(5)(4)(3));
     writeln(curry2(&foo)(5)(4)(3));
}



This is the code string generated by genChain() for the foo() 
function:

(immutable(int) x0) => (const(float) x1) => (short x2) => f(x0, 
x1, x2);


I think this code induces the creation of heap allocated 
closures, so probably a more efficient version is needed:

_D4test24__T5curryTPFNaNbyixfs...
L0: push EAX
     push EAX
     push EBX
     push 8
     call near ptr __d_allocmemory
     mov  EBX,EAX
     mov  EAX,0Ch[ESP]
     mov  [EBX],EAX
     fld  float ptr 014h[ESP]
     mov  EAX,EBX
     mov  EDX,offset FLAT:_D4test24__T5curryTPFNaNbyixf...
     fstp float ptr 4[EBX]
     add  ESP,4
     pop  EBX
     add  ESP,8
     ret  4


If the function is:

double bar(ref int x, ref double y) pure nothrow {
     x++;
     return x * 2 + y * 3;
}


it generates:

(int x0) => (double x1) => f(x0, x1);

So this version doesn't handle ref arguments.

Bye,
bearophile
Jun 18 2012
next sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 06/18/12 22:24, bearophile wrote:

 I think std.functional.curry is badly named because I think it's a "partial
application" (I suggest to rename it).
 In Haskell and Scala currying is built-in, this is Haskell, shell (ghci):
 
 Prelude> let foo x y z = x * 2 + y * 3 + y * 5
 Prelude> let foo1 = foo 5
 Prelude> let foo2 = foo1 4
 Prelude> foo2 3
 42



 So I've written a D version of it below, not tested much. I have not
translated the C++11 version. This was quite easy to write, and much simpler
and shorter than the C++11 version (but maybe this misses something, this is
just a first draft). This kind of stuff was quite longer to do in D1, but now
with CTFE on strings ops, defining one or more inner static functions that
build a string at compile-time, it's quite easy. Now I don't need lot of
templates to do this.
 
 There are two alternative designs, curry1 seems a bit more elegant, but if you
want to use it in-place it forces you to add a () at the beginning, that's not
nice and intuitive. So probably curry2 is better.


[...]

 I think this code induces the creation of heap allocated closures, so probably
a more efficient version is needed:


I'm not really sure when you'd want to use this in D.
But, just to be able to say "Real Programmers don't use mixins": :)

   static struct curry(alias F) {
      import std.traits;
      ParameterTypeTuple!F args;
      template opCall1(size_t N=0) {
         auto ref opCall1(ParameterTypeTuple!F[N] a) {
            auto p = (cast(Unqual!(typeof(a))*)&args[N]);
            *p = a;
            static if (N==args.length-1)
               return F(args);
            else
               return &opCall1!(N+1);
         }
      }
      alias opCall1!() opCall;
      static curry opCall() { curry c; return c; }
   }
   //...    
   double foo(immutable int x, in float y, short z=5) pure nothrow {
      return x * 2 + y * 3 + y * 5;
   }
    
   auto cf = curry!foo();
   auto c2 = cf(5)(4);
   writeln(c2(3));
   curry!foo cf2;
   writeln(cf2(5)(4)(3));
   writeln(curry!foo()(5)(4)(3));


The empty parens could be omitted, but you'd need a compiler with full
property support for that (and of course would have to wrap this in a
function). No heap allocations, the resulting code could be better
though.


 So this version doesn't handle ref arguments.


Yeah, this one doesn't either; iterating and checking every arg would
probably be necessary.

artur
Jun 19 2012
prev sibling next sibling parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Tue, Jun 19, 2012 at 2:52 PM, Artur Skawina <art.08.09 gmail.com> wrote:


 I'm not really sure when you'd want to use this in D.


As for Haskell. For example, with a range of ranges and you want to
take the first 100 elements of all subranges:

alias Curry!take ctake;

auto target = [[0,1,2,...], [...], ];
auto first100s = map!(ctake(100))(target);

And so on. When mapping and filtering ranges, I need currying from
time to time.



 But, just to be able to say "Real Programmers don't use mixins": :)


I find Bearophile version quite nice. I did something equivalent a few
years ago, with string mixins also. Of course, the a => b syntax did
not exist then.
I
Jun 21 2012
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Philippe Sigaud:


 alias Curry!take ctake;

 auto target = [[0,1,2,...], [...], ];
 auto first100s = map!(ctake(100))(target);


The first argument of std.range.take is the range, this is handy 
for chaining with UFCS.

I think currently curry!take doesn't work because take is not a 
function (but maybe this is fixable).

Bye,
bearophile
Jun 21 2012
prev sibling next sibling parent "David Nadlinger" <see klickverbot.at> writes:
On Thursday, 21 June 2012 at 19:04:32 UTC, Philippe Sigaud wrote:

 On Tue, Jun 19, 2012 at 2:52 PM, Artur Skawina

 But, just to be able to say "Real Programmers don't use 
 mixins": :)


 I find Bearophile version quite nice. I did something 
 equivalent a few
 years ago, with string mixins also. […]


Using string mixins as done here isn't just no »real 
programmers« thing to do, it has very substantial problems.

The problem with bearophile's code is that it uses T.stringof to 
refer to the parameter, but in the real world – where the 
template is not defined in the same module as it is used from – 
this will not work, as the (non-builtin) argument types will 
simply not be in scope (the implementation couldn't possibly 
import all the modules the user could ever want to use types 
from, even ignoring Voldemort types and the likes for the moment).

I see this mistake – __traits(identifier, …) has just the 
same problem, by the way – being made so frequently even by 
experienced D programmers (IIRC dranges contains a few instances 
of it as well) that I wonder if there is anything we could do 
about it design-wise. At least, adding a big warning on how to 
_not_ use stringof/__traits(identifier, …) to the language docs 
seems like a good idea to me.

Coming back to this particular case, the issue is very easy to 
fix: just emit ParameterTypeTuple!F[i] instead of T.stringof from 
the mixin generating code.

As far as ref is concerned, I'm not aware of a universal way to 
handle it in the general case – I usually end up manually 
looking ref-ness up to generate code accordingly (see 
ParameterStorageClassTuple).

David
Jun 21 2012
prev sibling parent "David Nadlinger" <see klickverbot.at> writes:
On Thursday, 21 June 2012 at 19:04:32 UTC, Philippe Sigaud wrote:

 As for Haskell. For example, with a range of ranges and you 
 want to
 take the first 100 elements of all subranges:

 alias Curry!take ctake;

 auto target = [[0,1,2,...], [...], ];
 auto first100s = map!(ctake(100))(target);


To me, it seems like what you want here conceptually is partial 
application – it just happens to be equivalent to currying 
because the function has only two parameters.

I personally use partial application all the time, but never 
found myself in the need for currying so far. But maybe that's 
just because I don't have significant experience in Haskell and 
the likes.

David
Jun 21 2012
prev sibling next sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 06/21/12 21:04, Philippe Sigaud wrote:

 On Tue, Jun 19, 2012 at 2:52 PM, Artur Skawina <art.08.09 gmail.com> wrote:
 

 I'm not really sure when you'd want to use this in D.


 
 As for Haskell. For example, with a range of ranges and you want to
 take the first 100 elements of all subranges:
 
 alias Curry!take ctake;
 
 auto target = [[0,1,2,...], [...], ];
 auto first100s = map!(ctake(100))(target);
 
 And so on. When mapping and filtering ranges, I need currying from
 time to time.


Sure, but partial application would be enough for cases like this one.

   auto partappe(alias F, A...)(auto ref A a) {
      auto ref f(ParameterTypeTuple!F[0..$-A.length] b) { return F(b, a); }
      return &f;
   }
   
   int n = 2;
   auto target = [[0,1,2], [3,4,5], [6,7,8]];
   auto takeN = partappe!(take!(int[]))(n);
   auto firstN = map!takeN(target);

I wonder if there's a case for "real" currying in 'D'; still can't think
of one, but maybe that's just because it's not how i would usually code it.
   
artur
Jun 21 2012
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Jun 22, 2012 at 12:12 AM, Artur Skawina <art.08.09 gmail.com> wrote:


 Sure, but partial application would be enough for cases like this one.

 I wonder if there's a case for "real" currying in 'D'; still can't think
 of one, but maybe that's just because it's not how i would usually code it.


Ah yes, you're right of course.
Jun 21 2012