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