www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.functional.curry isn't

reply Graham Fawcett <fawcett uwindsor.ca> writes:
Hi folks,

The template "std.functional.curry(alias fun, alias arg)" claims to 
"curry fun by tying its first argument to a particular value."

That is not currying; it is partial application. In particular, it is a 
kind of partial application called a "left section," because the argument 
provided is partially applied as the left-hand argument of the binary 
function.

Partial application takes a binary function and a value, and returns a 
unary function.

Currying takes a binary function and returns a unary function, which 
returns a unary function.

Let [A,B]-> C be the type of binary functions taking arguments of types A 
and B, and returning a value of type C. A unary function from B to C can 
be written [B]->C.

left section:  [ ([A,B]->C), A ] -> ([B] -> C). 
right section: [ ([A,B]->C), B ] -> ([A] -> C). 
curry:         [ ([A,B]->C) ] -> ([A] -> ([B] -> C)).

The example in the std.functional documentation:

int fun(int a, int b) { return a + b; }
alias curry!(fun, 5) fun5;
assert(fun5(6) == 11);

If this were a real curry, you would write it like this:

int fun(int a, int b) { return a + b; }
assert(curry!(fun)(5)(6) == 11);

Confusing curring and partial application is a very common mistake. But 
please rename this template in std.functional. It makes the 
std.functional module look amateurish to have such an error.

I'd vote for "template partial(alias fun, alias arg)" and "template 
partialR(alias fun, alias arg)" for left and right sections. It's 
unlikely that you really need a "curry" template at all.

Regards,
Graham
Jun 24 2010
next sibling parent Bill Baxter <wbaxter gmail.com> writes:
On Thu, Jun 24, 2010 at 5:06 PM, Graham Fawcett <fawcett uwindsor.ca> wrote=
:
 Hi folks,

 The template "std.functional.curry(alias fun, alias arg)" claims to
 "curry fun by tying its first argument to a particular value."

 That is not currying; it is partial application. In particular, it is a
 kind of partial application called a "left section," because the argument
 provided is partially applied as the left-hand argument of the binary
 function.

 Partial application takes a binary function and a value, and returns a
 unary function.

 Currying takes a binary function and returns a unary function, which
 returns a unary function.

 Let [A,B]-> C be the type of binary functions taking arguments of types A
 and B, and returning a value of type C. A unary function from B to C can
 be written [B]->C.

 left section: =A0[ ([A,B]->C), A ] -> ([B] -> C).
 right section: [ ([A,B]->C), B ] -> ([A] -> C).
 curry: =A0 =A0 =A0 =A0 [ ([A,B]->C) ] -> ([A] -> ([B] -> C)).

 The example in the std.functional documentation:

 int fun(int a, int b) { return a + b; }
 alias curry!(fun, 5) fun5;
 assert(fun5(6) =3D=3D 11);

 If this were a real curry, you would write it like this:

 int fun(int a, int b) { return a + b; }
 assert(curry!(fun)(5)(6) =3D=3D 11);

 Confusing curring and partial application is a very common mistake. But
 please rename this template in std.functional. It makes the
 std.functional module look amateurish to have such an error.

 I'd vote for "template partial(alias fun, alias arg)" and "template
 partialR(alias fun, alias arg)" for left and right sections. It's
 unlikely that you really need a "curry" template at all.

 Regards,
 Graham

Agreed. I brought up the same thing back when curry() was just an example in the documentation of variadic templates. --bb
Jun 24 2010
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Graham Fawcett:
 If this were a real curry, you would write it like this:
 int fun(int a, int b) { return a + b; }
 assert(curry!(fun)(5)(6) == 11);

Right. Better to change the name. Regarding std.functional, are the HOF adjoin(), compose() and pipe() useful? I don't think I'll use compose() or pipe(). If not enough people find them useful, then they can be removed. There is something that instead I'd like added (that I am going to put as request in Bugzilla, maybe later today): Apply functionality is quite useful, as shown by this small Python program that prints "1, 2": def foo(x, y): print x, y tuple1 = (1, 2) foo(*tuple1) That star syntax of Python is equivalent to this, that works still in Python 2.x: apply(foo, tuple1) The star syntax can't be used in D, but a good apply() function can be useful in D too. There the tuple is of course a std.typecons.Tuple. Bye, bearophile
Jun 24 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/24/2010 07:37 PM, bearophile wrote:
 Graham Fawcett:
 If this were a real curry, you would write it like this: int
 fun(int a, int b) { return a + b; } assert(curry!(fun)(5)(6) ==
 11);

Right. Better to change the name.

I think it would be even better to redefine curry to do actual currying.
 Regarding std.functional, are the HOF adjoin(), compose() and pipe()
 useful? I don't think I'll use compose() or pipe(). If not enough
 people find them useful, then they can be removed.

I'm finding them quite useful, particularly in conjunction with e.g. map. Andrei
Jun 24 2010
parent bearophile <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 I think it would be even better to redefine curry to do actual currying.

Right.
 I'm finding them quite useful, particularly in conjunction with e.g. map.

Oh, OK. Then let's keep them :-) What do you think about the apply? Bye, bearophile
Jun 24 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/24/2010 07:06 PM, Graham Fawcett wrote:
 Hi folks,

 The template "std.functional.curry(alias fun, alias arg)" claims to
 "curry fun by tying its first argument to a particular value."

 That is not currying; it is partial application.

[...]
 Confusing curring and partial application is a very common mistake. But
 please rename this template in std.functional. It makes the
 std.functional module look amateurish to have such an error.

Hm, fine. The whole curry thing was an experiment that I put on hold because back then I couldn't support functions with any number of arguments, which puts a damp on enthusiasm. I suggest you to send a patch to bugzilla in case you have the time. Andrei
Jun 24 2010
next sibling parent reply Graham Fawcett <fawcett uwindsor.ca> writes:
On Thu, 24 Jun 2010 20:19:47 -0500, Andrei Alexandrescu wrote:

 On 06/24/2010 07:06 PM, Graham Fawcett wrote:
 Hi folks,

 The template "std.functional.curry(alias fun, alias arg)" claims to
 "curry fun by tying its first argument to a particular value."

 That is not currying; it is partial application.

[...]
 Confusing curring and partial application is a very common mistake. But
 please rename this template in std.functional. It makes the
 std.functional module look amateurish to have such an error.

Hm, fine. The whole curry thing was an experiment that I put on hold because back then I couldn't support functions with any number of arguments, which puts a damp on enthusiasm. I suggest you to send a patch to bugzilla in case you have the time. Andrei

Thank you. http://d.puremagic.com/issues/show_bug.cgi?id=4391 Best, Graham
Jun 25 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 06/25/2010 08:39 AM, Graham Fawcett wrote:
 On Thu, 24 Jun 2010 20:19:47 -0500, Andrei Alexandrescu wrote:

 On 06/24/2010 07:06 PM, Graham Fawcett wrote:
 Hi folks,

 The template "std.functional.curry(alias fun, alias arg)" claims to
 "curry fun by tying its first argument to a particular value."

 That is not currying; it is partial application.

[...]
 Confusing curring and partial application is a very common mistake. But
 please rename this template in std.functional. It makes the
 std.functional module look amateurish to have such an error.

Hm, fine. The whole curry thing was an experiment that I put on hold because back then I couldn't support functions with any number of arguments, which puts a damp on enthusiasm. I suggest you to send a patch to bugzilla in case you have the time. Andrei

Thank you. http://d.puremagic.com/issues/show_bug.cgi?id=4391

Great. I'm hoping for a patch that fixes the problem, but it's good to have the report we don't forget this. Andrei
Jun 25 2010
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--001636c5bf480066680489df94f6
Content-Type: text/plain; charset=ISO-8859-1

On Fri, Jun 25, 2010 at 16:36, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 On 06/25/2010 08:39 AM, Graham Fawcett wrote:

 Thank you.

 http://d.puremagic.com/issues/show_bug.cgi?id=4391

Great. I'm hoping for a patch that fixes the problem, but it's good to have the report we don't forget this.

I'm using this, without problem up to now, it works for n-args functions (even 0 or 1) and accepts template functions too, but see the doc for the limitation in this case. /** Takes a D function, and curries it (in traditional, mathematical sense): given a n-args function, it creates n 1-arg functions nested inside one another. When all original arguments are reached, it returns the result. Example: ---- int add(int i, int j) { return i+j;} alias curry!add cadd; // cadd waits for an int, will return an int delegate(int) auto add3 = cadd(3); // add3 is a function that take an int and return this int + 3. auto m = map!add3([0,1,2,3]); assert(equal(m, [3,4,5,6])); bool equals(int i, int j) { return i==j;} alias curry!equals cequals; auto equals4 = cequals(4); // equals4 is a function taking an int and return true iff this int is 4. auto f = filter!equals4([2,3,4,5,4,3,2,2,3,4]); assert(equal(f, [4,4,4])); ---- What's fun is that it'll work for template functions too. Example: ---- string conj(A, B)(A a, B b) { return to!string(a)~to!string(b); } alias curry!conj cconj; auto c1 = cconj(1); // c1 is a template function waiting for any type. assert(c1('a') == "1a"); ---- BUG: for now, it does not verify the compatibility of types while you give it the arguments. It's only at the end that it sees whether or not it can call the function with these arguments. Example: ---- // given a function like this, with dependencies between the arguments' types: A foo(A,B,C)(A a, Tuple!(B,A) b, Tuple!(C,B,A) c) { return a+b.field[1]+c.field[2];} // if you curries it and gives it an int as first argument, the returned template function should really be: int foo2(B,C)(Tuple!(B,int) b) { return anotherFunction;} // because we now know A to be an int... ---- */ template curry(alias fun) { static if (isFunction!fun) enum curry = mixin(curryImpl!(fun, "", ParameterTypeTuple!fun)); else enum curry = curriedFunction!(fun)(); } template curryImpl(alias fun, string xs, T...) { static if (T.length == 0) enum curryImpl = "&fun"; else static if (T.length == 1) enum curryImpl = "(" ~ T[0].stringof ~ " x1) { return fun(" ~ xs ~ "x1);}"; else enum curryImpl = "(" ~ T[0].stringof ~ " x" ~ to!string(T.length) ~ ") { return " ~ curryImpl!(fun,xs ~ "x" ~ to!string(T.length) ~ ", ", T[1..$]) ~ ";}"; } struct CurriedFunction(alias fun, T...) /+if (T.length)+/ { T _t; static if (T.length) void initialize(T t) { _t = t;} template OpCallType(U...) { static if (is (typeof(fun(Init!T, Init!U)))) alias typeof(fun(Init!T, Init!U)) OpCallType; else alias CurriedFunction!(fun, T, U) OpCallType; } OpCallType!U opCall(U...)(U u) { static if(is(typeof(fun(_t, u)))) return fun(_t,u); else { CurriedFunction!(fun, T, U) cf; static if (U.length) cf.initialize(_t, u); return cf; } } } CurriedFunction!(fun, TypeTuple!()) curriedFunction(alias fun)() { CurriedFunction!(fun, TypeTuple!()) cf; return cf; } unittest { int add(int i, int j) { return i+j;} alias curry!add cadd; // cadd waits for an int, will return an int delegate(int) auto add3 = cadd(3); // add3 is a function that take an int and return this int + 3. auto m = map!add3([0,1,2,3]); assert(equal(m, [3,4,5,6])); bool equals(int i, int j) { return i==j;} alias curry!equals cequals; auto equals4 = cequals(4); // equals4 is a function taking an int and return true iff this int is 4. auto f = filter!equals4([2,3,4,5,4,3,2,2,3,4]); assert(equal(f, [4,4,4])); } So, the template function part is still a bit rough. I've plan to keep track of types dependencies, but ... well, Real Life (tm) is in the way. I posted it as a comment in the bug report, in case it can help someone write something. Philippe --001636c5bf480066680489df94f6 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On Fri, Jun 25, 2010 at 16:36, Andrei Alexandres= cu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">S= eeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br><blockquote class=3D"= gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb= (204, 204, 204); padding-left: 1ex;"> <div><div></div><div class=3D"h5">On 06/25/2010 08:39 AM, Graham Fawcett wr= ote:<br> <blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0.8ex; borde= r-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Thank you.<br> <br> <a href=3D"http://d.puremagic.com/issues/show_bug.cgi?id=3D4391" target=3D"= _blank">http://d.puremagic.com/issues/show_bug.cgi?id=3D4391</a><br> </blockquote> <br></div></div> Great. I&#39;m hoping for a patch that fixes the problem, but it&#39;s good= to have the report we don&#39;t forget this.<font color=3D"#888888"></font=
</blockquote><div><br>I&#39;m using this, without problem up to now, it wo=

but see the doc for the limitation in this case.<br> <br><br>/**<br>Takes a D function, and curries it (in traditional, mathemat= ical sense): given<br>a n-args function, it creates n 1-arg functions neste= d inside one another. When<br>all original arguments are reached, it return= s the result.<br> <br>Example:<br>----<br>int add(int i, int j) { return i+j;}<br>alias curry= !add cadd; // cadd waits for an int, will return an int delegate(int)<br>au= to add3 =3D cadd(3); // add3 is a function that take an int and return this= int + 3.<br> <br>auto m =3D map!add3([0,1,2,3]);<br>assert(equal(m, [3,4,5,6]));<br><br>= bool equals(int i, int j) { return i=3D=3Dj;}<br>alias curry!equals cequals= ;<br>auto equals4 =3D cequals(4); // equals4 is a function taking an int an= d return true iff this int is 4.<br> auto f =3D filter!equals4([2,3,4,5,4,3,2,2,3,4]);<br>assert(equal(f, [4,4,4= ]));<br>----<br><br>What&#39;s fun is that it&#39;ll work for template func= tions too.<br><br>Example:<br>----<br>string conj(A, B)(A a, B b)<br>{<br> =A0=A0=A0 return to!string(a)~to!string(b);<br>}<br><br>alias curry!conj cc= onj;<br>auto c1 =3D cconj(1); // c1 is a template function waiting for any = type.<br>assert(c1(&#39;a&#39;) =3D=3D &quot;1a&quot;);<br>----<br>BUG:<br>= for now, it does not verify the compatibility of types while you give it th= e arguments. It&#39;s only<br> at the end that it sees whether or not it can call the function with these = arguments.<br>Example:<br>----<br>// given a function like this, with depen= dencies between the arguments&#39; types:<br>A foo(A,B,C)(A a, Tuple!(B,A) = b, Tuple!(C,B,A) c) { return a+b.field[1]+c.field[2];}<br> // if you curries it and gives it an int as first argument, the returned te= mplate function should really be:<br>int foo2(B,C)(Tuple!(B,int) b) { retur= n anotherFunction;}<br>// because we now know A to be an int...<br>----<br> */<br>template curry(alias fun)<br>{<br>=A0=A0=A0 static if (isFunction!fun= )<br>=A0=A0=A0=A0=A0=A0=A0 enum curry =3D=A0 mixin(curryImpl!(fun, &quot;&q= uot;, ParameterTypeTuple!fun));<br>=A0=A0=A0 else<br>=A0=A0=A0=A0=A0=A0=A0 = enum curry =3D curriedFunction!(fun)();<br> }<br><br>template curryImpl(alias fun, string xs, T...)<br>{<br>=A0=A0=A0 s= tatic if (T.length =3D=3D 0)<br>=A0=A0=A0=A0=A0=A0=A0 enum curryImpl =3D &q= uot;&amp;fun&quot;;<br>=A0=A0=A0 else static if (T.length =3D=3D 1)<br>=A0= =A0=A0=A0=A0=A0=A0 enum curryImpl =3D &quot;(&quot; ~ T[0].stringof=A0 ~ &q= uot; x1) { return fun(&quot; ~ xs ~ &quot;x1);}&quot;;<br> =A0=A0=A0 else<br>=A0=A0=A0=A0=A0=A0=A0 enum curryImpl =3D &quot;(&quot; ~ = T[0].stringof=A0 ~ &quot; x&quot; ~ to!string(T.length) ~ &quot;) { return = &quot;<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0= =A0=A0=A0=A0=A0=A0 ~ curryImpl!(fun,xs ~ &quot;x&quot; ~ to!string(T.length= ) ~ &quot;, &quot;, T[1..$]) ~ &quot;;}&quot;;<br> }<br><br>struct CurriedFunction(alias fun, T...) /+if (T.length)+/<br>{<br>= =A0=A0=A0 T _t;<br>=A0=A0=A0 static if (T.length)<br>=A0=A0=A0=A0=A0=A0=A0 = void initialize(T t) { _t =3D t;}<br><br>=A0=A0=A0 template OpCallType(U...= )<br>=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0 static if (is (typeof(fun(Init!T,= Init!U))))<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 alias typeof(fun(Init!T, Init!U)) OpCallT= ype;<br>=A0=A0=A0=A0=A0=A0=A0 else<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ali= as CurriedFunction!(fun, T, U) OpCallType;<br>=A0=A0=A0 }<br><br>=A0=A0=A0 = OpCallType!U opCall(U...)(U u)<br>=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0 stat= ic if(is(typeof(fun(_t, u))))<br> =A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 return fun(_t,u);<br>=A0=A0=A0=A0=A0=A0= =A0 else<br>=A0=A0=A0=A0=A0=A0=A0 {<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 Cu= rriedFunction!(fun, T, U) cf;<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 static i= f (U.length) cf.initialize(_t, u);<br>=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0=A0 ret= urn cf;<br>=A0=A0=A0=A0=A0=A0=A0 }<br>=A0=A0=A0 }<br>}<br><br> CurriedFunction!(fun, TypeTuple!()) curriedFunction(alias fun)()<br>{<br>= =A0=A0=A0 CurriedFunction!(fun, TypeTuple!()) cf;<br>=A0=A0=A0 return cf;<b= r>}<br><br>unittest<br>{<br>=A0=A0=A0 int add(int i, int j) { return i+j;}<= br>=A0=A0=A0 alias curry!add cadd; // cadd waits for an int, will return an= int delegate(int)<br> =A0=A0=A0 auto add3 =3D cadd(3); // add3 is a function that take an int and= return this int + 3.<br><br>=A0=A0=A0 auto m =3D map!add3([0,1,2,3]);<br>= =A0=A0=A0 assert(equal(m, [3,4,5,6]));<br><br>=A0=A0=A0 bool equals(int i, = int j) { return i=3D=3Dj;}<br> =A0=A0=A0 alias curry!equals cequals;<br>=A0=A0=A0 auto equals4 =3D cequals= (4); // equals4 is a function taking an int and return true iff this int is= 4.<br>=A0=A0=A0 auto f =3D filter!equals4([2,3,4,5,4,3,2,2,3,4]);<br>=A0= =A0=A0 assert(equal(f, [4,4,4]));<br> }<br>=A0<br><br>So, the template function part is still a bit rough. I&#39;= ve plan to keep track of types dependencies, but ... well, Real Life (tm) i= s in the way.<br><br>I posted it as a comment in the bug report, in case it= can help someone write something.<br> <br>Philippe<br><br></div></div> --001636c5bf480066680489df94f6--
Jun 25 2010