Generator/Exponential

Generator/Exponential is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A generator is an executable entity (like a function or procedure) that contains code that yields a sequence of values, one at a time, so that each time you call the generator, the next value in the sequence is provided. Generators are often built on top of coroutines or objects so that the internal state of the object is handled “naturally”. Generators are often used in situations where a sequence is potentially infinite, and where it is possible to construct the next value of the sequence with only minimal state.

Task description

1. Create a function returning a generator of the m'th powers of the positive integers starting from zero, in order, and without obvious or simple upper limit. (Any upper limit to the generator should not be stated in the source but should be down to factors such as the languages natural integer size limit or computational time/size).
2. Use it to create a generator of:

1. Squares.
2. Cubes.

1. Create a new generator that filters all cubes from the generator of squares.
2. Drop the first 20 values from this last generator of filtered results then show the next 10 values

Note that this task requires the use of generators in the calculation of the result.

See also

• Generator

Ada

Works with: Ada 2005

generator.ads: <lang Ada>package Generator is

  type Generator is tagged private;
  procedure Reset (Gen : in out Generator);
  function Get_Next (Gen : access Generator) return Natural;

  type Generator_Function is access function (X : Natural) return Natural;
  procedure Set_Generator_Function (Gen  : in out Generator;
                                    Func : Generator_Function);

  procedure Skip (Gen : access Generator'Class; Count : Positive := 1);

private

  function Identity (X : Natural) return Natural;

  type Generator is tagged record
     Last_Source : Natural := 0;
     Last_Value  : Natural := 0;
     Gen_Func    : Generator_Function := Identity'Access;
  end record;

end Generator;</lang>

generator-filtered.ads: <lang Ada>package Generator.Filtered is

  type Filtered_Generator is new Generator with private;
  procedure Reset (Gen : in out Filtered_Generator);
  function Get_Next (Gen : access Filtered_Generator) return Natural;

  procedure Set_Source (Gen    : in out Filtered_Generator;
                        Source : access Generator);
  procedure Set_Filter (Gen    : in out Filtered_Generator;
                        Filter : access Generator);

private

  type Filtered_Generator is new Generator with record
     Last_Filter : Natural := 0;
     Source, Filter : access Generator;
  end record;

end Generator.Filtered;</lang>

generator.adb: <lang Ada>package body Generator is

  --------------
  -- Identity --
  --------------

  function Identity (X : Natural) return Natural is
  begin
     return X;
  end Identity;

  ----------
  -- Skip --
  ----------

  procedure Skip (Gen : access Generator'Class; Count : Positive := 1) is
     Val : Natural;
     pragma Unreferenced (Val);
  begin
     for I in 1 .. Count loop
        Val := Gen.Get_Next;
     end loop;
  end Skip;

  -----------
  -- Reset --
  -----------

  procedure Reset (Gen : in out Generator) is
  begin
     Gen.Last_Source := 0;
     Gen.Last_Value := 0;
  end Reset;

  --------------
  -- Get_Next --
  --------------

  function Get_Next (Gen : access Generator) return Natural is
  begin
     Gen.Last_Source := Gen.Last_Source + 1;
     Gen.Last_Value := Gen.Gen_Func (Gen.Last_Source);
     return Gen.Last_Value;
  end Get_Next;

  ----------------------------
  -- Set_Generator_Function --
  ----------------------------

  procedure Set_Generator_Function
    (Gen  : in out Generator;
     Func : Generator_Function)
  is
  begin
     if Func = null then
        Gen.Gen_Func := Identity'Access;
     else
        Gen.Gen_Func := Func;
     end if;
  end Set_Generator_Function;

end Generator;</lang>

generator-filtered.adb: <lang Ada>package body Generator.Filtered is

  -----------
  -- Reset --
  -----------

  procedure Reset (Gen : in out Filtered_Generator) is
  begin
     Reset (Generator (Gen));
     Gen.Source.Reset;
     Gen.Filter.Reset;
     Gen.Last_Filter := 0;
  end Reset;

  --------------
  -- Get_Next --
  --------------

  function Get_Next (Gen : access Filtered_Generator) return Natural is
     Next_Source : Natural := Gen.Source.Get_Next;
     Next_Filter : Natural := Gen.Last_Filter;
  begin
     loop
        if Next_Source > Next_Filter then
           Gen.Last_Filter := Gen.Filter.Get_Next;
           Next_Filter := Gen.Last_Filter;
        elsif Next_Source = Next_Filter then
           Next_Source := Gen.Source.Get_Next;
        else
           return Next_Source;
        end if;
     end loop;
  end Get_Next;

  ----------------
  -- Set_Source --
  ----------------

  procedure Set_Source
    (Gen    : in out Filtered_Generator;
     Source : access Generator)
  is
  begin
     Gen.Source := Source;
  end Set_Source;

  ----------------
  -- Set_Filter --
  ----------------

  procedure Set_Filter
    (Gen    : in out Filtered_Generator;
     Filter : access Generator)
  is
  begin
     Gen.Filter := Filter;
  end Set_Filter;

end Generator.Filtered;</lang>

example use: <lang Ada>with Ada.Text_IO; with Generator.Filtered;

procedure Generator_Test is

  function Square (X : Natural) return Natural is
  begin
     return X * X;
  end Square;

  function Cube (X : Natural) return Natural is
  begin
     return X * X * X;
  end Cube;

  G1, G2 : aliased Generator.Generator;
  F : aliased Generator.Filtered.Filtered_Generator;

begin

  G1.Set_Generator_Function (Func => Square'Unrestricted_Access);
  G2.Set_Generator_Function (Func => Cube'Unrestricted_Access);

  F.Set_Source (G1'Unrestricted_Access);
  F.Set_Filter (G2'Unrestricted_Access);

  F.Skip (20);

  for I in 1 .. 10 loop
     Ada.Text_IO.Put ("I:" & Integer'Image (I));
     Ada.Text_IO.Put (", F:" & Integer'Image (F.Get_Next));
     Ada.Text_IO.New_Line;
  end loop;

end Generator_Test;</lang>

output:

I: 1, F: 529
I: 2, F: 576
I: 3, F: 625
I: 4, F: 676
I: 5, F: 784
I: 6, F: 841
I: 7, F: 900
I: 8, F: 961
I: 9, F: 1024
I: 10, F: 1089

C

Library: libco

libco is a tiny library that adds cooperative multithreading, also known as coroutines, to the C language. Its co_switch(x) function pauses the current cothread and resumes the other cothread x.

This example provides next64() and yield64(), to generate 64-bit integers. next64() switches to a generator. Then the generator passes some 64-bit integer to yield64(), which switches to the first cothread, where next64() returns this 64-bit integer.

<lang c>#include <inttypes.h> /* int64_t, PRId64 */

1. include <stdlib.h> /* exit() */
2. include <stdio.h> /* printf() */

1. include <libco.h> /* co_{active,create,delete,switch}() */

/* A generator that yields values of type int64_t. */ struct gen64 { cothread_t giver; /* this cothread calls yield64() */ cothread_t taker; /* this cothread calls next64() */ int64_t given; void (*free)(struct gen64 *); void *garbage; };

/* Yields a value. */ inline void yield64(struct gen64 *gen, int64_t value) { gen->given = value; co_switch(gen->taker); }

/* Returns the next value that the generator yields. */ inline int64_t next64(struct gen64 *gen) { gen->taker = co_active(); co_switch(gen->giver); return gen->given; }

static void gen64_free(struct gen64 *gen) { co_delete(gen->giver); }

struct gen64 *entry64;

/*

* Creates a cothread for the generator. The first call to next64(gen)
* will enter the cothread; the entry function must copy the pointer
* from the global variable struct gen64 *entry64.
*
* Use gen->free(gen) to free the cothread.
*/

inline void gen64_init(struct gen64 *gen, void (*entry)(void)) { if ((gen->giver = co_create(4096, entry)) == NULL) { /* Perhaps malloc() failed */ fputs("co_create: Cannot create cothread\n", stderr); exit(1); } gen->free = gen64_free; entry64 = gen; }

/*

* Generates the powers 0**m, 1**m, 2**m, ....
*/

void powers(struct gen64 *gen, int64_t m) { int64_t base, exponent, n, result;

for (n = 0;; n++) { /* * This computes result = base**exponent, where * exponent is a nonnegative integer. The result * is the product of repeated squares of base. */ base = n; exponent = m; for (result = 1; exponent != 0; exponent >>= 1) { if (exponent & 1) result *= base; base *= base; } yield64(gen, result); } /* NOTREACHED */ }

/* stuff for squares_without_cubes() */

1. define ENTRY(name, code) static void name(void) { code; }

ENTRY(enter_squares, powers(entry64, 2)) ENTRY(enter_cubes, powers(entry64, 3))

struct swc { struct gen64 cubes; struct gen64 squares; void (*old_free)(struct gen64 *); };

static void swc_free(struct gen64 *gen) { struct swc *f = gen->garbage; f->cubes.free(&f->cubes); f->squares.free(&f->squares); f->old_free(gen); }

/*

* Generates the squares 0**2, 1**2, 2**2, ..., but removes the squares
* that equal the cubes 0**3, 1**3, 2**3, ....
*/

void squares_without_cubes(struct gen64 *gen) { struct swc f; int64_t c, s;

gen64_init(&f.cubes, enter_cubes); c = next64(&f.cubes);

gen64_init(&f.squares, enter_squares); s = next64(&f.squares);

/* Allow other cothread to free this generator. */ f.old_free = gen->free; gen->garbage = &f; gen->free = swc_free;

for (;;) { while (c < s) c = next64(&f.cubes); if (c != s) yield64(gen, s); s = next64(&f.squares); } /* NOTREACHED */ }

ENTRY(enter_squares_without_cubes, squares_without_cubes(entry64))

/*

* Look at the sequence of numbers that are squares but not cubes.
* Drop the first 20 numbers, then print the next 10 numbers.
*/

int main() { struct gen64 gen; int i;

gen64_init(&gen, enter_squares_without_cubes);

for (i = 0; i < 20; i++) next64(&gen); for (i = 0; i < 9; i++) printf("%" PRId64 ", ", next64(&gen)); printf("%" PRId64 "\n", next64(&gen));

gen.free(&gen); /* Free memory. */ return 0; }</lang>

One must download libco and give libco.c to the compiler.

$ libco=/home/kernigh/park/libco
$ cc -I$libco -o main main.c $libco/libco.c
$ ./main
529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089

D

Ranges version: <lang d>import std.stdio, std.bigint, std.range;

struct Filtered(R1, R2) if (is(ElementType!R1 == ElementType!R2)) {

   R1 s1;
   R2 s2;
   alias ElementType!R1 T;
   T current, source, filter;

   this(R1 r1, R2 r2) {
       s1 = r1;
       s2 = r2;
       source = s1.front();
       filter = s2.front();
       _next();
   }

   const bool empty = false;
   T front() { return current; }
   void popFront() { _next(); }

   private void _next() {
       while (true) {
           if (source > filter) {
               s2.popFront();
               filter = s2.front();
               continue;
           } else if (source < filter) {
               current = source;
               s1.popFront();
               source = s1.front();
               break;
           }
           s1.popFront();
           source = s1.front();
       }
   }

}

auto filtered(R1, R2)(R1 r1, R2 r2) if (is(ElementType!R1 == ElementType!R2)) {

   return Filtered!(R1, R2)(r1, r2);

}

struct Powers {

   int m;
   BigInt n; // = 0;
   const bool empty = false;
   BigInt front() { return n ^^ m; }
   void popFront() { n+= 1; }

}

void main() {

   auto squares = Powers(2);
   auto cubes = Powers(3);
   auto f = filtered(squares, cubes);
   popFrontN(f, 20);
   writeln(take(f, 10));

}</lang> Output:

[529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

From the Go version: <lang d>import std.stdio;

auto powers(double e) {

   double i = 0.0;
   return { return i++ ^^ e; };

}

auto filter(D)(D af, D bf) {

   double a = af(), b = bf();
   return {
       double r;
       while (true) {
           if (a < b) {
               r = a;
               a = af();
               break;
           }
           if (b == a)
               a = af();
           b = bf();
       }
       return r;
   };

}

void main() {

   auto fgen = filter(powers(2), powers(3));
   foreach (i; 0 .. 20)
       fgen();
   foreach (i; 0 .. 10)
       write(fgen(), " ");
   writeln();

}</lang> Output:

529 576 625 676 784 841 900 961 1024 1089 

E

E does not provide coroutines on the principle that interleaving of execution of code should be explicit to avoid unexpected interactions. However, this problem does not especially require them. Each generator here is simply a function that returns the next value in the sequence when called.

<lang e>def genPowers(exponent) {

   var i := -1
   return def powerGenerator() {
       return (i += 1) ** exponent
   }

}

def filtered(source, filter) {

   var fval := filter()
   return def filterGenerator() {
       while (true) {
           def sval := source()
           while (sval > fval) {
               fval := filter()
           }
           if (sval < fval) {
               return sval
           }
       }
   }

}

def drop(n, gen) {

   for _ in 1..n { gen() }

}

def squares := genPowers(2) def cubes := genPowers(3) def squaresNotCubes := filtered(squares, cubes) drop(20, squaresNotCubes) for _ in 1..10 {

   print(`${squaresNotCubes()} `)

} println()</lang>

Go

Most direct and most efficient on a single core is implementing generators with closures. <lang go>package main

import (

   "fmt"
   "math"

)

// note: exponent not limited to ints func newPowGen(e float64) func() float64 {

   var i float64
   return func() (r float64) {
       r = math.Pow(i, e)
       i++
       return
   }

}

// given two functions af, bf, both monotonically increasing, return a // new function that returns values of af not returned by bf. func newMonoIncA_NotMonoIncB_Gen(af, bf func() float64) func() float64 {

   a, b := af(), bf()
   return func() (r float64) {
       for {
           if a < b {
               r = a
               a = af()
               break
           }
           if b == a {
               a = af()
           }
           b = bf()
       }
       return
   }

}

func main() {

   fGen := newMonoIncA_NotMonoIncB_Gen(newPowGen(2), newPowGen(3))
   for i := 0; i < 20; i++ {
       fGen()
   }
   for i := 0; i < 10; i++ {
       fmt.Print(fGen(), " ")
   }
   fmt.Println("")

}</lang> Output:

529 576 625 676 784 841 900 961 1024 1089

Haskell

Generators in most cases can be implemented using infinite lists in Haskell. Because Haskell is lazy, only as many elements as needed is computed from the infinite list: <lang haskell>powers m = map (^ m) [0..]

filtered (x:xs) (y:ys) | x > y = filtered (x:xs) ys

                      | x < y = x : filtered xs (y:ys)
                      | otherwise = filtered xs (y:ys)

squares = powers 2 cubes = powers 3 f = filtered squares cubes

main :: IO () main = print $ take 10 $ drop 20 $ f</lang>

Sample output

[529,576,625,676,784,841,900,961,1024,1089]

Icon and Unicon

Generators are close to the heart and soul of Icon/Unicon. Co-expressions let us circumvent the normal backtracking mechanism and get results where we need them.

<lang Icon>procedure main()

write("Non-cube Squares (21st to 30th):") every (k := 0, s := noncubesquares()) do

  if(k +:= 1) > 30 then break
  else write(20 < k," : ",s)  

end

procedure mthpower(m) #: generate i^m for i = 0,1,... while (/i := 0) | (i +:= 1) do suspend i^m end

procedure noncubesquares() #: filter for squares that aren't cubes cu := create mthpower(3) # co-expressions so that we can sq := create mthpower(2) # ... get our results where we need

repeat {

  if c === s then  ( c := @cu , s := @sq ) 
  else if s > c then c := @cu
  else {
     suspend s
     s := @sq 
     }
  }

end</lang>

Note: The task could be written without co-expressions but would be likely be ugly. If there is an elegant non-co-expression version please add it as an alternate example.

Output:

Non-cube Squares (21st to 30th):
21 : 529
22 : 576
23 : 625
24 : 676
25 : 784
26 : 841
27 : 900
28 : 961
29 : 1024
30 : 1089

J

Generators are not very natural, in J, because they avoid the use of arrays and instead rely on sequential processing.

Here is a generator for mth powers of a number:

<lang j>coclass 'mthPower'

 N=: 0
 create=: 3 :0
   M=: y
 )
 next=: 3 :0
   n=. N
   N=: N+1
   n^M
 )</lang>

And, here are corresponding square and cube generators

<lang j>stateySquare=: 2 conew 'mthPower' stateyCube=: 3 conew 'mthPower'</lang>

Here is a generator for squares which are not cubes:

<lang j>coclass 'uncubicalSquares'

 N=: 0
 next=: 3 :0"0
   while. (-: <.) 3 %: *: n=. N do. N=: N+1 end. N=: N+1
   *: n
 )</lang>

And here is an example of its use:

<lang j> next__g i.10 [ next__g i.20 [ g=: conew 'uncubicalSquares' 529 576 625 676 784 841 900 961 1024 1089</lang>

That said, here is a more natural approach, for J.

<lang j>mthPower=: 1 :'^&m@i.' squares=: 2 mthPower cubes=: 3 mthPower uncubicalSquares=: squares -. cubes</lang>

The downside of this approach is that it is computing independent sequences. And for the "uncubicalSquares" verb, it is removing some elements from that sequence. So you must estimate how many values to generate. However, this can be made transparent to the user with a simplistic estimator:

<lang j>uncubicalSquares=: {. squares@<.@p.~&3 1.1 -. cubes</lang>

Example use:

<lang j>20 }. uncubicalSquares 30 529 576 625 676 784 841 900 961 1024 1089</lang>

Lua

Generators can be implemented both as closures or as coroutines. The following example demonstrates both.

<lang Lua> --could be done with a coroutine, but a simple closure works just as well. local function powgen(m)

 local count = 0
 return function()
   count = count + 1
   return count^m
 end

end

local squares = powgen(2) local cubes = powgen(3)

local cowrap,coyield = coroutine.wrap, coroutine.yield

local function filter(f,g)

 return cowrap(function()
   local ff,gg = f(), g()
   while true do
     if ff == gg then
       ff,gg = f(), g()
     elseif ff < gg then
       coyield(ff)
       ff = f()
     else
       gg = g()
     end
   end
 end)

end

filter = filter(squares,cubes)

for i = 1,30 do

 local result = filter()
 if i > 20 then
   print(result)
 end

end </lang>

Perl

These generators are anonymous subroutines, which are closures.

<lang perl># gen_pow($m) creates and returns an anonymous subroutine that will

1. generate and return the powers 0**m, 1**m, 2**m, ...

sub gen_pow {

   my $m = shift;
   my $e = 0;
   return sub { return $e++ ** $m; };

}

1. gen_filter($g1, $g2) generates everything returned from $g1 that
2. is not also returned from $g2. Both $g1 and $g2 must be references
3. to subroutines that generate numbers in increasing order. gen_filter
4. creates and returns an anonymous subroutine.

sub gen_filter {

   my($g1, $g2) = @_;
   my $v1;
   my $v2 = $g2->();
   return sub {
       for (;;) {
           $v1 = $g1->();
           $v2 = $g2->() while $v1 > $v2;
           return $v1 unless $v1 == $v2;
       }
   };

}

1. Create generators.

my $squares = gen_pow(2); my $cubes = gen_pow(3); my $squares_without_cubes = gen_filter($squares, $cubes);

1. Drop 20 values.

$squares_without_cubes->() for (1..20);

1. Print 10 values.

my @answer; push @answer, $squares_without_cubes->() for (1..10); print "[", join(", ", @answer), "]\n";</lang>

Output:

[529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

Perl 6

As with Haskell, generators are disguised as lazy lists in Perl 6. <lang perl6>sub powers($m) { 0..* X** $m }

my @squares := powers(2); my @cubes  := powers(3);

sub infix:<without> (@orig,@veto) {

   gather for @veto -> $veto {
       take @orig.shift while @orig[0] before $veto;
       @orig.shift if @orig[0] eqv $veto;
   }

}

say (@squares without @cubes)[20 ..^ 20+10].join(', ');</lang>

Output:

529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089

PicoLisp

Coroutines are available only in the 64-bit version. <lang PicoLisp>(de powers (M)

  (co (intern (pack 'powers M))
     (for (I 0 (inc 'I))
        (yield (** I M)) ) ) )

(de filtered (N M)

  (co 'filtered
     (let (V (powers N)  F (powers M))
        (loop
           (if (> V F)
              (setq F (powers M))
              (and (> F V) (yield V))
              (setq V (powers N)) ) ) ) ) )

(do 20 (filtered 2 3)) (do 10 (println (filtered 2 3)))</lang> Output:

529
576
625
676
784
841
900
961
1024
1089

Python

In Python, any function that contains a yield statement becomes a generator. The standard libraries itertools module provides the following functions used in the solution: count, that will count up from zero; and islice, which will take a slice from an iterator/generator.

<lang python>from itertools import islice, count

def powers(m):

   for n in count():
       yield n ** m
   

def filtered(s1, s2):

   n1, n2 = s1.__next__, s2.__next__
   v, f = n1(), n2()
   while True:
       if v > f:
           f = n2()
           continue
       elif v < f:
           yield v
       v = n1()

squares, cubes = powers(2), powers(3) f = filtered(squares, cubes) print(list(islice(f, 20, 30)))</lang>

Sample output

[529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

Ruby

This first solution cheats and uses only one generator! It has three iterators powers(2), powers(3) and squares_without_cubes, but the only generator runs powers(3).

An iterator is a Ruby method that takes a block parameter, and loops the block for each element. So powers(2) { |i| puts "Got #{i}" } would loop forever and print Got 0, Got 1, Got 4, Got 9 and so on. Starting with Ruby 1.8.7, one can use Object#enum_for to convert an iterator method to an Enumerator object. The Enumerator#next method is a generator that runs the iterator method on a separate coroutine. Here cubes.next generates the next cube number.

Works with: Ruby version 1.8.7

<lang ruby># This solution cheats and uses only one generator!

def powers(m)

 return enum_for(:powers, m) unless block_given?

 n = 0
 loop { yield n ** m; n += 1 }

end

def squares_without_cubes

 return enum_for(:squares_without_cubes) unless block_given?

 cubes = powers(3)
 c = cubes.next
 powers(2) do |s|
   (c = cubes.next) until c >= s
   yield s unless c == s
 end

end

p squares_without_cubes.take(30).drop(20)</lang>

Output: [529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

---

Here is the correct solution, which obeys the requirement of three generators.

Works with: Ruby version 1.8.7

<lang ruby># This solution uses three generators.

def powers(m)

 return enum_for(:powers, m) unless block_given?

 n = 0
 loop { yield n ** m; n += 1 }

end

def squares_without_cubes

 return enum_for(:squares_without_cubes) unless block_given?

 cubes = powers(3)
 c = cubes.next
 squares = powers(2)
 loop do
   s = squares.next
   (c = cubes.next) until c >= s
   yield s unless c == s
 end

end

answer = squares_without_cubes 20.times { answer.next } p (1..10).map { answer.next }</lang>

Output: [529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

If we change both programs to drop the first 1_000_020 values (output: [1000242014641, 1000244014884, 1000246015129, 1000248015376, 1000250015625, 1000252015876, 1000254016129, 1000256016384, 1000258016641, 1000260016900]), then the one-generator solution runs much faster than the three-generator solution on a machine with MRI 1.9.2.

Tcl

Works with: Tcl version 8.6

Tcl implements generators in terms of coroutines. If these generators were terminating, they would finish by doing return -code break so as to terminate the calling loop context that is doing the extraction of the values from the generator. <lang tcl>package require Tcl 8.6

proc powers m {

   yield
   for {set n 0} true {incr n} {

yield [expr {$n ** $m}]

   }

} coroutine squares powers 2 coroutine cubes powers 3 coroutine filtered apply {{s1 s2} {

   yield
   set f [$s2]
   set v [$s1]
   while true {

if {$v > $f} { set f [$s2] continue } elseif {$v < $f} { yield $v } set v [$s1]

   }

}} squares cubes

1. Drop 20

for {set i 0} {$i<20} {incr i} {filtered}

1. Take/print 10

for {} {$i<30} {incr i} {

   puts [filtered]

}</lang> Output:

529
576
625
676
784
841
900
961
1024
1089