www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Code from a Rosetta Code Task

reply "Meta" <jared771 gmail.com> writes:
uint fib(in uint n) pure nothrow {
     immutable self = &__traits(parent, {});
     return (n < 2) ? n : self(n - 1) + self(n - 2);
}

I came across this while browsing Rosetta Code. It's really cool 
how you can do recursion without anonymous functions (and this 
will actually not work if you make fib a delegate). However, I'm 
confused about the __traits(parent, {}) part, specifically , the 
{} passed to parent. Does {} just mean the outer scope?
Aug 29 2013
parent reply "Robik" <nomail foo.com> writes:
On Thursday, 29 August 2013 at 18:57:58 UTC, Meta wrote:
 uint fib(in uint n) pure nothrow {
     immutable self = &__traits(parent, {});
     return (n < 2) ? n : self(n - 1) + self(n - 2);
 }

 I came across this while browsing Rosetta Code. It's really 
 cool how you can do recursion without anonymous functions (and 
 this will actually not work if you make fib a delegate). 
 However, I'm confused about the __traits(parent, {}) part, 
 specifically , the {} passed to parent. Does {} just mean the 
 outer scope?
{} in this case is just empty delegate function.
Aug 29 2013
next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Aug 29, 2013 at 11:00:49PM +0200, Robik wrote:
 On Thursday, 29 August 2013 at 18:57:58 UTC, Meta wrote:
uint fib(in uint n) pure nothrow {
    immutable self = &__traits(parent, {});
    return (n < 2) ? n : self(n - 1) + self(n - 2);
}

I came across this while browsing Rosetta Code. It's really cool
how you can do recursion without anonymous functions (and this
will actually not work if you make fib a delegate). However, I'm
confused about the __traits(parent, {}) part, specifically , the
{} passed to parent. Does {} just mean the outer scope?
{} in this case is just empty delegate function.
That's clever, but I'm not sure I understand the bit about anonymous functions? You don't need anonymous functions to have recursion. Also, this is a pretty poor algorithm for generating the Fibonacci series, as it has exponential time complexity in addition to linear space complexity. It's even worse than the recursive factorial function, which at least doesn't have exponential time complexity. T -- Leather is waterproof. Ever see a cow with an umbrella?
Aug 29 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:

 Also, this is a pretty poor algorithm for generating the 
 Fibonacci series,
I know, but you must do what the tasks asks you: http://rosettacode.org/wiki/Anonymous_recursion Bye, bearophile
Aug 29 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Fri, Aug 30, 2013 at 01:37:39AM +0200, bearophile wrote:
 H. S. Teoh:
 
Also, this is a pretty poor algorithm for generating the Fibonacci
series,
I know, but you must do what the tasks asks you: http://rosettacode.org/wiki/Anonymous_recursion
[...] OK I see. I wish we could reeducate people that recursive Fibonacci algorithms are Bad(tm). :) There are better examples of recursion that don't have poor performance characteristics, or where no better alternative exists. Like parsing expression trees, for example (even though the parser can be recursive, it is only linear in the size of the input, so it's not bad). T -- I think the conspiracy theorists are out to get us...
Aug 29 2013
prev sibling parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 08/29/2013 04:37 PM, bearophile wrote:

 H. S. Teoh:

 Also, this is a pretty poor algorithm for generating the Fibonacci
 series,
I know, but you must do what the tasks asks you: http://rosettacode.org/wiki/Anonymous_recursion Bye, bearophile
Hm... Like some of the other language implementations, D's is not correct. There is a misunderstanding. Note that they say "which checks for a negative argument before doing the actual recursion." The problem that is described is this case (note that the parameter is negative to make the problem meaningful): // Actual recursive function int fib_R(int n) pure nothrow { // Please ignore the algorithmic complexity issue. :) return (n < 2) ? n : fib_R(n - 1) + fib_R(n - 2); } // The non-recursive API function that calls the recursive one int fib(int n) pure { enforce(n >= 0); return fib_R(n); } So the problem is asking for a solution for the problem of having to write two separate functions. Ali
Aug 29 2013
prev sibling parent reply "Meta" <jared771 gmail.com> writes:
On Thursday, 29 August 2013 at 22:01:38 UTC, H. S. Teoh wrote:
 That's clever, but I'm not sure I understand the bit about 
 anonymous functions? You don't need anonymous functions to have 
 recursion.
Sorry, that came out all wrong. What I meant was that it's neat to be able to do anonymous recursion without having to resort to tricks like the Y-Combinator. However, after some fiddling, it seems that this is actually not usable with anonymous functions, or at least, I couldn't find a way to do it.
Aug 29 2013
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 08/29/2013 08:53 PM, Meta wrote:

 However, after some fiddling, it seems that this is actually not 
usable with
 anonymous functions, or at least, I couldn't find a way to do it.
Borrowing the "self" trick from the existing solution, the following satisfies all of the requirements: int fib(int arg) pure { enforce(arg >= 0); return function int (int n) pure nothrow { auto self = __traits(parent, {}); return (n < 2) ? n : self(n - 1) + self(n - 2); }(arg); } Ali
Aug 29 2013
prev sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Thu, Aug 29, 2013 at 03:00:09PM -0700, H. S. Teoh wrote:
 On Thu, Aug 29, 2013 at 11:00:49PM +0200, Robik wrote:
 On Thursday, 29 August 2013 at 18:57:58 UTC, Meta wrote:
uint fib(in uint n) pure nothrow {
    immutable self = &__traits(parent, {});
    return (n < 2) ? n : self(n - 1) + self(n - 2);
}

I came across this while browsing Rosetta Code. It's really cool
how you can do recursion without anonymous functions (and this
will actually not work if you make fib a delegate). However, I'm
confused about the __traits(parent, {}) part, specifically , the
{} passed to parent. Does {} just mean the outer scope?
{} in this case is just empty delegate function.
That's clever, but I'm not sure I understand the bit about anonymous functions? You don't need anonymous functions to have recursion. Also, this is a pretty poor algorithm for generating the Fibonacci series, as it has exponential time complexity in addition to linear space complexity. It's even worse than the recursive factorial function, which at least doesn't have exponential time complexity.
[...] A far better implementation is to use std.range.recurrence: uint fib(in uint n) pure nothrow { return recurrence!((a,n) => a[n-2] + a[n-1])(1, 1) .drop(n-1) .front; } This implementation has linear time complexity and constant space complexity (vs. exponential time complexity vs. linear space complexity in the original). To illustrate how bad it is, I wrote a program that calls fib(50) for each of the above implementations, and observed how long it takes each one to return an answer. The version using recurrence completes in a fraction of a second, the second takes two *minutes*. I bumped it up to fib(100), and the recurrence version still runs under a fraction of a second, but I ran out of patience waiting for the second one. I would like to promote the use of std.range.recurrence instead of monstrous exponential-time algorithms like the recursive fib(), or the horrible linear-space recursive factorial. The latter can also be reduced to linear time complexity + constant space complexity thanks to std.range.recurrence: uint factorial(in uint n) pure nothrow { return recurrence!((a,n) => n * a[n-1])(1) .drop(n-1) .front; } *This* should be the selling point of D: the fact that you can write nice mathematical recurrences like that and still have it generate highly-efficient code, not the fact that you can do some clever tricks with __traits but end up with horrible exponential-time algorithms. T -- The irony is that Bill Gates claims to be making a stable operating system and Linus Torvalds claims to be trying to take over the world. -- Anonymous
Aug 29 2013
parent Jos van Uden <usenet fwend.com> writes:
On 30-8-2013 0:40, H. S. Teoh wrote:
(...)
 A far better implementation is to use std.range.recurrence:

 	uint fib(in uint n) pure nothrow {
 		return recurrence!((a,n) => a[n-2] + a[n-1])(1, 1)
 			.drop(n-1)
 			.front;
 	}

 This implementation has linear time complexity and constant space
 complexity (vs. exponential time complexity vs. linear space complexity
 in the original).

 To illustrate how bad it is, I wrote a program that calls fib(50) for
 each of the above implementations, and observed how long it takes each
 one to return an answer. The version using recurrence completes in a
 fraction of a second, the second takes two *minutes*. I bumped it up to
 fib(100), and the recurrence version still runs under a fraction of a
 second, but I ran out of patience waiting for the second one.
(...) http://www.wolframalpha.com/input/?i=fib(100) void main() { import std.bigint, std.range; BigInt fib(in uint fibN) pure { return recurrence!((a,n) => a[n-2] + a[n-1])(BigInt(1), BigInt(1)) .drop(fibN-1) .front; } assert(fib(100) == BigInt("354_224_848_179_261_915_075")); } nice
Aug 30 2013