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