Re: Lambda functions in D
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?
Re: Lambda functions in D
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.)
Re: Lambda functions in D
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
Re: Lambda functions in D
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? It turns out that 2.067 fixes the integrality of BigInts so: reduce!"a * b"(one, iota(BigInt(one), n + one)); works fine – one is immutable(BigInt(1)). Many interesting performance issues around using take versus iota. -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder signature.asc Description: This is a digitally signed message part
Re: Lambda functions in D
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
Re: Lambda functions in D
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.
Re: Lambda functions in D
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.
Re: Lambda functions in D
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. -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder signature.asc Description: This is a digitally signed message part
Re: Lambda functions in D
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
Re: Lambda functions in D
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 :)
Re: Lambda functions in D
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);
Re: Lambda functions in D
Dennis Ritchie wrote: auto fact = function (int x) => x * { if (x) fact(x - 1); }; int fact (int x) { return x * ( x>1 ? fact(x - 1): 1); }; -manfred
Re: Lambda functions in D
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.
Lambda functions in D
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); }