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

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 thread and resumes the other thread x.

This example adds 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 thread, where next64() returns this 64-bit integer.

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

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

1. include <libco.h> /* co_active(), co_create(), co_switch() */

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

/* 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; }

struct gen64 *entry64;

/*

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

inline void gen64_init(struct gen64 *gen, void (*entry)(void)) { gen->giver = co_create(4096, entry); entry64 = gen; }

/* Defines a static entry function for a coroutine. */

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

/*

* 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 */ }

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

/*

* 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 gen64 cubes, squares; int64_t c, s;

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

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

for (;;) { if (c != s) yield64(gen, s); while (c <= s) c = next64(&cubes); s = next64(&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));

/* * This program has no way to free the memory for all three * coroutines. It can do co_delete(gen.giver) but then there * would be no way to free the other two coroutines for squares * and cubes. * * Here the program exits, to free the memory for the entire * program. */ 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

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

Generators can be implemented directly in Go by a channel fed by a goroutine.

Thus a "function returning a generator" corresponds to a function that creates a channel, starts a goroutine that will send values on the channel, and returns the channel. The function powCh does this, starting a function literal as the goroutine. The returned channel corresponds to a generator.

The "generator that filters..." is implemented without an extra function, simply by creating the channel and starting a (previously declared) function as a goroutine. Here too, the created channel, chF, corresponds to a generator, once the goroutine has be started for it. <lang go>package main

import (

   "fmt"
   "math"

)

// note: exponent not limited to ints func powCh(e float64) <-chan float64 {

   ch := make(chan float64)
   go func() {
       // generate powers of non-negative integers
       for i := float64(0); ; i++ {
           ch <- math.Pow(i, e)
       }
   }()
   return ch

}

// this long function name to indicate that the filtering // logic works only because squares and cubes are both // monotonically increasing over the specified domain // of non-negative integers. func genMonotonicIncA_NotMonotonicIncB(outCh chan<- float64, aCh, bCh <-chan float64) {

   for a, b := <-aCh, <-bCh; ; {
       if a > b {
           b = <-bCh
           continue
       } else if a < b {
           outCh <- a
       }
       a = <-aCh
   }

}

func main() {

   // square and cube generators
   chSq := powCh(2)
   chCu := powCh(3)

   // filtered generator (in two lines)
   chF := make(chan float64)
   go genMonotonicIncA_NotMonotonicIncB(chF, chSq, chCu)

   // collect results
   for i := 0; i < 20; i++ {
       <-chF
   }
   for i := 0; i < 10; i++ {
       fmt.Print(<-chF, " ")
   }
   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]

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>

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|
   yield s unless c == s
   (c = cubes.next) until 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
   yield s unless c == s
   (c = cubes.next) until 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