www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Lambda functions in D

reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
Hi,
Can lambda functions or delegates in D to call themselves?
Can I write something like this:

-----
import std.stdio;

void main() {

	auto fact = function (int x) => x * { if (x) fact(x - 1); };

	assert(fact(10) == 3628800);
}
May 09 2015
next sibling parent "tcak" <tcak gmail.com> writes:
On Saturday, 9 May 2015 at 11:20:10 UTC, Dennis Ritchie wrote:
 Hi,
 Can lambda functions or delegates in D to call themselves?
 Can I write something like this:

 -----
 import std.stdio;

 void main() {

 	auto fact = function (int x) => x * { if (x) fact(x - 1); };

 	assert(fact(10) == 3628800);
 }
dmd says no.
May 09 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/09/2015 01:20 PM, Dennis Ritchie wrote:
 Hi,
 Can lambda functions or delegates in D to call themselves?
 Can I write something like this:

 -----
 import std.stdio;

 void main() {

      auto fact = function (int x) => x * { if (x) fact(x - 1); };

      assert(fact(10) == 3628800);
 }
assert((function int(int x)=>x?x*__traits(parent,{})(x-1):1)(10)==3628800);
May 09 2015
parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Saturday, 9 May 2015 at 11:49:48 UTC, Timon Gehr wrote:
 assert((function int(int 
 x)=>x?x*__traits(parent,{})(x-1):1)(10)==3628800);
Thanks. Yes, it is similar to what I wanted :)
May 09 2015
parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/09/2015 04:59 AM, Dennis Ritchie wrote:
 On Saturday, 9 May 2015 at 11:49:48 UTC, Timon Gehr wrote:
 assert((function int(int
 x)=>x?x*__traits(parent,{})(x-1):1)(10)==3628800);
Thanks. Yes, it is similar to what I wanted :)
Also interesting: http://rosettacode.org/wiki/Y_combinator#D I think that code was improved by Timon Gehr as well. Ali
May 09 2015
next sibling parent reply Russel Winder via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Sat, 2015-05-09 at 07:15 -0700, Ali =C3=87ehreli via Digitalmars-d-learn=
 wrote:
 On 05/09/2015 04:59 AM, Dennis Ritchie wrote:
 On Saturday, 9 May 2015 at 11:49:48 UTC, Timon Gehr wrote:
 assert((function int(int
 x)=3D>x?x*__traits(parent,{})(x-1):1)(10)=3D=3D3628800);
=20 Thanks. Yes, it is similar to what I wanted :)
=20 Also interesting: =20 http://rosettacode.org/wiki/Y_combinator#D =20 I think that code was improved by Timon Gehr as well. =20 Ali
Sadly all the solutions are unsound since they are recursive but not tail recursive. Oh it doesn't matter as D doesn't have tail call optimization. There are lots of good imperative implementations. Of course none of the implementation can calculate factorial(24) as they are using hardware values which are bounded and cannot store reasonable numbers. Could use iota. Oh no we can't as BigNums are not integral. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
May 09 2015
next sibling parent "John Colvin" <john.loughran.colvin gmail.com> writes:
On Saturday, 9 May 2015 at 14:47:21 UTC, Russel Winder wrote:
 On Sat, 2015-05-09 at 07:15 -0700, Ali Çehreli via 
 Digitalmars-d-learn wrote:
 On 05/09/2015 04:59 AM, Dennis Ritchie wrote:
 On Saturday, 9 May 2015 at 11:49:48 UTC, Timon Gehr wrote:
 assert((function int(int
 x)=>x?x*__traits(parent,{})(x-1):1)(10)==3628800);
Thanks. Yes, it is similar to what I wanted :)
Also interesting: http://rosettacode.org/wiki/Y_combinator#D I think that code was improved by Timon Gehr as well. Ali
Sadly all the solutions are unsound since they are recursive but not tail recursive. Oh it doesn't matter as D doesn't have tail call optimization. There are lots of good imperative implementations. Of course none of the implementation can calculate factorial(24) as they are using hardware values which are bounded and cannot store reasonable numbers. Could use iota. Oh no we can't as BigNums are not integral.
you could probably use sequence, or even recurrence.
May 09 2015
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/09/2015 07:47 AM, Russel Winder via Digitalmars-d-learn wrote:

 Of course none of the implementation can calculate factorial(24) as
 they are using hardware values which are bounded and cannot store
 reasonable numbers.

 Could use iota. Oh no we can't as BigNums are not integral.
I don't have experience with BigInt but the following worked: import std.stdio; import std.bigint; import std.range; import std.algorithm; struct BigIntRange { BigInt front; enum empty = false; void popFront() { ++front; } } BigIntRange bigInts(long first = 0) { return BigIntRange(BigInt(first)); } BigInt factorial(size_t n) { return bigInts(1).take(n).reduce!((a, b) => a *= b); } void main() { writeln(factorial(1000)); // prints many digits } Ali
May 09 2015
parent reply Russel Winder via Digitalmars-d-learn <digitalmars-d-learn puremagic.com> writes:
On Sat, 2015-05-09 at 09:49 -0700, Ali =C3=87ehreli via Digitalmars-d-learn=
 wrote:
=20
[=E2=80=A6]
 BigInt factorial(size_t n)
 {
      return bigInts(1).take(n).reduce!((a, b) =3D> a *=3D b);
 }
I wonder if that should be a * b rather than a *=3D b? It turns out that 2.067 fixes the integrality of BigInts so: reduce!"a * b"(one, iota(BigInt(one), n + one)); works fine =E2=80=93 one is immutable(BigInt(1)). Many interesting performance issues around using take versus iota. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
May 09 2015
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 05/09/2015 10:45 AM, Russel Winder via Digitalmars-d-learn wrote:
 On Sat, 2015-05-09 at 09:49 -0700, Ali Çehreli via Digitalmars-d-learn wrote:

 […]
 BigInt factorial(size_t n)
 {
       return bigInts(1).take(n).reduce!((a, b) => a *= b);
 }
I wonder if that should be a * b rather than a *= b?
Yes. :) Luckily, the difference is an unused side-effect to parameter 'a' in my wrong version. Ali
May 09 2015
prev sibling parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Saturday, 9 May 2015 at 14:15:21 UTC, Ali Çehreli wrote:
 On 05/09/2015 04:59 AM, Dennis Ritchie wrote:
 On Saturday, 9 May 2015 at 11:49:48 UTC, Timon Gehr wrote:
 assert((function int(int
 x)=>x?x*__traits(parent,{})(x-1):1)(10)==3628800);
Thanks. Yes, it is similar to what I wanted :)
Also interesting: http://rosettacode.org/wiki/Y_combinator#D I think that code was improved by Timon Gehr as well. Ali
Yes, it's much better. Even something like Common Lisp.
May 09 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 05/09/2015 05:52 PM, Dennis Ritchie wrote:
 On Saturday, 9 May 2015 at 14:15:21 UTC, Ali Çehreli wrote:
 On 05/09/2015 04:59 AM, Dennis Ritchie wrote:
 On Saturday, 9 May 2015 at 11:49:48 UTC, Timon Gehr wrote:
 assert((function int(int
 x)=>x?x*__traits(parent,{})(x-1):1)(10)==3628800);
Thanks. Yes, it is similar to what I wanted :)
Also interesting: http://rosettacode.org/wiki/Y_combinator#D I think that code was improved by Timon Gehr as well. Ali
Yes, it's much better.
Well, it is much slower due to all the allocated closures, owed to the fact that the implementations of 'fix' on that page are expected to mirror a particular famous implementation in untyped lambda calculus. In case you have a use for 'fix', a more efficient implementation might be: auto fix(S,T...)(S delegate(T) delegate (S delegate(T)) f){ S delegate(T) g=(T a){ assert(0,"f is too eager."); }; return g=f((T a)=>g(a)); } (In particular, this will only allocate two closures for the plumbing instead of a number of them linear in the number of recursive invocations.)
 Even something like Common Lisp.
(Be aware that Common Lisp implementations typically have better garbage collectors than what is available for D.)
May 09 2015
parent "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Saturday, 9 May 2015 at 21:48:05 UTC, Timon Gehr wrote:
 Well, it is much slower due to all the allocated closures, owed 
 to the fact that the implementations of 'fix' on that page are 
 expected to mirror a particular famous implementation in 
 untyped lambda calculus.

 In case you have a use for 'fix', a more efficient 
 implementation might be:

 auto fix(S,T...)(S delegate(T) delegate (S delegate(T)) f){
     S delegate(T) g=(T a){ assert(0,"f is too eager."); };
     return g=f((T a)=>g(a));
 }

 (In particular, this will only allocate two closures for the 
 plumbing instead of a number of them linear in the number of 
 recursive invocations.)


 Even something like Common Lisp.
(Be aware that Common Lisp implementations typically have better garbage collectors than what is available for D.)
Maybe in the future, that D will be added to optimize tail recursion delegates? And why garbage collectors in Lisp is better?
May 09 2015