pure generators

Simen kjaeraas simen.kjaras at gmail.com
Thu May 13 05:03:38 PDT 2010

```bearophile <bearophileHUGS at lycos.com> wrote:

>> This has to do with D iteration being more designed towards mimicking C
>> arrays.<
>
> I am not able to see the link between the two things.

An array is something you can use several times. The opApply
functionality is based on this behavior (not necessarily, but the common
usage, and specifically your usage in the provided code).

For something more like the Python generators, look at D2 ranges. An
example of those, for this specific usage, is included below.

>> (x for x in xrange(2,N) if all(x % i for i in xrange(2,x)))
>
>> Except that it also changes the input.
>
> The input there is N, and it doesn't get changed.
> You can see a pure generator like a pure function that returns an array
> of items. The main difference is that the items of such array are
> computed & given lazily.

Your input to creating the generator, yes. After that, the generator is
its own input. So the constructor is pure, its workings beyond that
point are not.

The equivalent in D would be a struct with a member function that does
not change any external variables, but does change internal state. Not
pure the way D has defined that word (Calling the function several
times with the same input does not yield the same output, unless you're
willing to call a different input with the same name the same input.).

>> Here's an implementation that seems to work:<
>
> The code worth traslating in D2 was the Haskell Fibonacci generator.
> Thank you for your code, but it's too much noisy, in normal situations I
> am not willing to write similar code.

Now, the right way to write a Fibonacci generator in D is this:

import std.range;
...
auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1);

Also, updated code below. It's now a range, and supports much cleaner
initialization and use:

import std.range;
import std.stdio;
import std.array;
import std.math;

class YieldingFiber( T ) : Fiber {
this( void function( ) fn ) {
super( fn );
call( );
}

this( void delegate( ) fn ) {
super( fn );
call( );
}

T call( ) {
if ( auto o = super.call( ) ) {
throw o;
}
return _value;
}

@property
T front( ) const {
return _value;
}

alias call popFront;

@property
bool empty( ) {
return state == Fiber.State.TERM;
}

static void yield( T value ) {
if ( auto p = cast( typeof( this ) )getThis( ) ) {
p._value = value;
} else {
throw new Exception( "Invalid yield type." );
}
Fiber.yield( );
}
private:
T _value;
}

void yield( T )( T value ) {
YieldingFiber!( T ).yield( value );
}

YieldingFiber!( T ) generator( T, U )( U fn ) {
return new YieldingFiber!( T )( fn );
}
// Non-reusable code from here.
void primes( ) {
loop:
for ( int x = 2; ; ++x ) {
foreach ( i; 2..ceil( sqrt( x + 0.0 ) ) ) {
if ( !( x % i ) ) {
continue loop;
}
}
yield( x );
}
}

void main( ) {
auto p = generator!( int )( &primes );
writeln( "Primes:" );
writeln( array( take( p, 20 ) ) );
auto fib = generator!int({ int a = 1, b = 1; while ( 1 ){ yield( a );
int c = a+b; a = b; b = c; } });
writeln( "Fibonacci:" );
writeln( array( take( fib, 20 ) ) );
}

Please note that the YieldingFiber class and the yield and generator
functions, are generic and not something one would need to reimplement each
time one wants a generator.

--
Simen
```