Generator/Exponential

From Rosetta Code
< Generator(Redirected from Generator)
Jump to: navigation, search
Task
Generator/Exponential
You are encouraged to solve this task according to the task description, using any language you may know.
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 that returns a generation 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

Contents

[edit] Ada

Works with: Ada 2005

To modify the internal state, the function uses an access parameter. For a different approach, see the Random packages of the Ada compiler, which use the so-called "Rosen trick". With the next release of Ada 2012 functions are allowed to have in-out parameters, which would solve this problem, too. You could also use procedures instead of functions.

generator.ads:

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;

generator-filtered.ads:

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;

generator.adb:

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;

generator-filtered.adb:

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;

example use:

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;

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

[edit] ALGOL 68

Translation of: Python
Works with: ALGOL 68 version Revision 1 - with currying of functions and PRAGMA READ extensions
Works with: ALGOL 68G version Any - tested with release algol68g-2.3.5.
File: Template.Generator.a68
MODE YIELDVALUE = PROC(VALUE)VOID;
MODE GENVALUE = PROC(YIELDVALUE)VOID;
 
PROC gen filtered = (GENVALUE gen candidate, gen exclude, YIELDVALUE yield)VOID: (
VALUE candidate; SEMA have next exclude = LEVEL 0;
VALUE exclude; SEMA get next exclude = LEVEL 0;
BOOL initialise exclude := TRUE;
 
PAR ( # run each generator in a different thread #
# Thread 1 #
# FOR VALUE next exclude IN # gen exclude( # ) DO #
## (VALUE next exclude)VOID: (
DOWN get next exclude; exclude := next exclude;
IF candidate <= exclude THEN
UP have next exclude
ELSE
UP get next exclude
FI
# OD #)),
# Thread 2 #
# FOR VALUE next candidate IN # gen candidate( # ) DO #
## (VALUE next candidate)VOID: (
candidate := next candidate;
IF initialise exclude ORF candidate > exclude THEN
UP get next exclude;
DOWN have next exclude; # wait for result #
initialise exclude := FALSE
FI;
IF candidate < exclude THEN
yield(candidate)
FI
# OD #))
)
);
 
PROC gen slice = (GENVALUE t, VALUE start, stop, YIELDVALUE yield)VOID: (
INT index := 0;
# FOR VALUE i IN # t( # ) DO #
## (VALUE i)VOID: (
IF index >= stop THEN done
ELIF index >= start THEN yield(i) FI;
index +:= 1
# OD # ));
done: SKIP
);
 
PROC get list = (GENVALUE gen)[]VALUE: (
INT upb := 0;
INT ups := 2;
FLEX [ups]VALUE out;
# FOR VALUE i IN # gen( # ) DO #
## (VALUE i)VOID:(
upb +:= 1;
IF upb > ups THEN # dynamically grow the array 50% #
[ups +:= ups OVER 2]VALUE append; append[:upb-1] := out; out := append
FI;
out[upb] := i
# OD # ))
out[:upb]
);
 
PROC powers = (VALUE m, YIELDVALUE yield)VOID:
FOR n FROM 0 DO yield(n ** m) OD;
File: test.Generator.a68
#!/usr/local/bin/a68g --script #
 
MODE VALUE = INT;
PR READ "Template.Generator.a68" PR
 
GENVALUE squares = powers(2,), cubes = powers(3,);
GENVALUE fil = gen filtered(squares, cubes,);
 
printf(($g(0)x$, get list(gen slice(fil, 20, 30, )) ))
Output:
529 576 625 676 784 841 900 961 1024 1089 

[edit] C

[edit]
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.

#include <inttypes.h>	/* int64_t, PRId64 */
#include <stdlib.h> /* exit() */
#include <stdio.h> /* printf() */
 
#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() */
#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;
}

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

[edit] Using struct to store state

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef int (*seq_func)(void *);
#define SEQ_BASE seq_func f; int output
 
/* sort of polymorphing data structure */
typedef struct { SEQ_BASE; } gen_t;
 
int seq_next(void *state)
{
return ((gen_t*)state)->output = (*(seq_func*)state)(state);
}
 
typedef struct {
SEQ_BASE;
int pos, n;
} power_gen_t;
 
int power_next(void *s)
{
return (int)pow(++((power_gen_t*)s)->pos, ((power_gen_t*)s)->n);
}
 
void *power_seq(int n)
{
power_gen_t *s = malloc(sizeof(power_gen_t));
s->output = -1;
s->f = power_next;
s->n = n;
s->pos = -1;
return s;
}
 
typedef struct {
SEQ_BASE;
void *in, *without;
} filter_gen_t;
 
int filter_next(void *s)
{
gen_t *in = ((filter_gen_t*)s)->in, *wo = ((filter_gen_t*)s)->without;
 
do{
seq_next(in);
while (wo->output < in->output)
seq_next(wo);
} while(wo->output == in->output);
 
return in->output;
}
 
void* filter_seq(gen_t *in, gen_t *without)
{
filter_gen_t *filt = malloc(sizeof(filter_gen_t));
filt->in = in;
filt->without = without;
filt->f = filter_next;
filt->output = -1;
return filt;
}
 
int main()
{
int i;
void *s = filter_seq(power_seq(2), power_seq(3));
 
for (i = 0; i < 20; i++) seq_next(s);
for (i = 0; i < 10; i++)
printf("%d\n", seq_next(s));
 
return 0;
}
output
529
576
625
676
784
841
900
961
1024
1089

[edit] C++

A templated solution.

#include <iostream>
using namespace std;
 
template<class T>
class Generator
{
public:
virtual T operator()() = 0;
};
 
// Does nothing unspecialized
template<class T, T P>
class PowersGenerator: Generator<T> {};
 
// Specialize with other types, or provide a generic version of pow
template<int P>
class PowersGenerator<int, P>: Generator<int>
{
public:
int i;
PowersGenerator() { i = 1; }
virtual int operator()()
{
int o = 1;
for(int j = 0; j < P; ++j) o *= i;
++i;
return o;
}
};
 
// Only works with non-decreasing generators
template<class T, class G, class F>
class Filter: Generator<T>
{
public:
G gen;
F filter;
T lastG, lastF;
 
Filter() { lastG = gen(); lastF = filter(); }
 
virtual T operator()()
{
while(lastG >= lastF)
{
if(lastG == lastF)
lastG = gen();
lastF = filter();
}
 
T out = lastG;
lastG = gen();
return out;
}
};
 
int main()
{
Filter<int, PowersGenerator<int, 2>, PowersGenerator<int, 3>> gen;
 
for(int i = 0; i < 20; ++i)
gen();
 
for(int i = 20; i < 30; ++i)
cout << i << ": " << gen() << endl;
}

Output:

20: 529
21: 576
22: 625
23: 676
24: 784
25: 841
26: 900
27: 961
28: 1024
29: 1089

[edit] C#

using System;
using System.Collections.Generic;
using System.Linq;
 
static class Program {
static void Main() {
Func<int, IEnumerable<int>> ms = m => Infinite().Select(i => (int)Math.Pow(i, m));
var squares = ms(2);
var cubes = ms(3);
var filtered = squares.Where(square => cubes.First(cube => cube >= square) != square);
var final = filtered.Skip(20).Take(10);
foreach (var i in final) Console.WriteLine(i);
}
 
static IEnumerable<int> Infinite() {
var i = 0;
while (true) yield return i++;
}
}

[edit] Clojure

In Clojure, the role that generator functions take in some other languages is generally filled by sequences. Most of the functions that produce sequences produce lazy sequences, many of the standard functions deal with sequences, and their use in Clojure is extremely idiomatic. Thus we can define squares and cubes as lazy sequences:

(defn powers [m] (for [n (iterate inc 1)] (reduce * (repeat m n)))))
(def squares (powers 2))
(take 5 squares) ; => (1 4 9 16 25)

The definition here of the squares-not-cubes lazy sequence uses the loop/recur construct, which isn't lazy. So we use lazy-seq explicity:

(defn squares-not-cubes 
([] (squares-not-cubes (powers 2) (powers 3)))
([squares cubes]
(loop [[p2first & p2rest :as p2s] squares, [p3first & p3rest :as p3s] cubes]
(cond
(= p2first p3first) (recur p2rest p3rest)
(> p2first p3first) (recur p2s p3rest)
 :else (cons p2first (lazy-seq (squares-not-cubes p2rest p3s)))))))
 
(->> (squares-not-cubes) (drop 20) (take 10))
; => (529 576 625 676 784 841 900 961 1024 1089)

If we really need a generator function for some reason, any lazy sequence can be turned into a stateful function. (The inverse of seq->fn is the standard function repeatedly.)

(defn seq->fn [sequence]
(let [state (atom (cons nil sequence))]
(fn [] (first (swap! state rest)))
 
(def f (seq->fn (squares-not-cubes)))
[(f) (f) (f)] ; => [4 9 16]

[edit] Common Lisp

(defun take (seq &optional (n 1))
(values-list (loop repeat n collect (funcall seq))))
 
(defun power-seq (n)
(let ((x 0))
(lambda () (expt (incf x) n))))
 
(defun filter-seq (s1 s2) ;; remove s2 from s1
(let ((x1 (take s1)) (x2 (take s2)))
(lambda ()
(tagbody g
(if (= x1 x2)
(progn (setf x1 (take s1) x2 (take s2)) (go g)))
(if (> x1 x2)
(progn (setf x2 (take s2)) (go g))))
 
(prog1 x1 (setf x1 (take s1))))))
 
(let ((2not3 (filter-seq (power-seq 2) (power-seq 3))))
(take 2not3 20) ;; drop 20
(princ (multiple-value-list (take 2not3 10))))

[edit] D

[edit] Efficient Standard Version

void main() {
import std.stdio, std.bigint, std.range, std.algorithm;
 
auto squares = 0.sequence!"n".map!(i => i.BigInt ^^ 2);
auto cubes = 0.sequence!"n".map!(i => i.BigInt ^^ 3);
 
squares.setDifference(cubes).drop(20).take(10).writeln;
}
Output:
[529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

[edit] Simple Ranges-Based Implementation

Translation of: C#
void main() {
import std.stdio, std.bigint, std.range, std.algorithm;
 
auto squares = 0.sequence!"n".map!(i => i.BigInt ^^ 2);
auto cubes = 0.sequence!"n".map!(i => i.BigInt ^^ 3);
 
squares
.filter!(s => cubes.find!(c => c >= s).front != s)
.drop(20)
.take(10)
.writeln;
}

The output is the same.

[edit] More Efficient Ranges-Based Version

import std.stdio, std.bigint, std.range, std.algorithm;
 
struct Filtered(R1, R2) if (is(ElementType!R1 == ElementType!R2)) {
R1 s1;
R2 s2;
alias ElementType!R1 T;
T front, source, filter;
 
this(R1 r1, R2 r2) {
s1 = r1;
s2 = r2;
source = s1.front;
filter = s2.front;
popFront;
}
 
static immutable empty = false;
 
void popFront() {
while (true) {
if (source > filter) {
s2.popFront;
filter = s2.front;
continue;
} else if (source < filter) {
front = source;
s1.popFront;
source = s1.front;
break;
}
s1.popFront;
source = s1.front;
}
}
}
 
auto filtered(R1, R2)(R1 r1, R2 r2) // Helper function.
if (isInputRange!R1 && isInputRange!R2 &&
is(ElementType!R1 == ElementType!R2)) {
return Filtered!(R1, R2)(r1, r2);
}
 
void main() {
auto squares = 0.sequence!"n".map!(i => i.BigInt ^^ 2);
auto cubes = 0.sequence!"n".map!(i => i.BigInt ^^ 3);
filtered(squares, cubes).drop(20).take(10).writeln;
}

The output is the same.

[edit] Closures-Based Version

Translation of: Go
import std.stdio;
 
auto powers(in double e) pure nothrow {
double i = 0;
return () => i++ ^^ e;
}
 
auto filter2(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 = filter2(2.powers, 3.powers);
foreach (immutable i; 0 .. 20)
fgen();
foreach (immutable i; 0 .. 10)
write(fgen(), " ");
writeln;
}
Output:
529 576 625 676 784 841 900 961 1024 1089 

[edit] 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.

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()

[edit] Erlang

 
-module( generator ).
 
-export( [filter/2, next/1, power/1, task/0] ).
 
filter( Source_pid, Remove_pid ) ->
First_remove = next( Remove_pid ),
erlang:spawn( fun() -> filter_loop(Source_pid, Remove_pid, First_remove) end ).
 
next( Pid ) ->
Pid ! {next, erlang:self()},
receive X -> X end.
 
power( M ) -> erlang:spawn( fun() -> power_loop(M, 0) end ).
 
task() ->
Squares_pid = power( 2 ),
Cubes_pid = power( 3 ),
Filter_pid = filter( Squares_pid, Cubes_pid ),
[next(Filter_pid) || _X <- lists:seq(1, 20)],
[next(Filter_pid) || _X <- lists:seq(1, 10)].
 
 
filter_loop( Pid1, Pid2, N2 ) ->
receive
{next, Pid} ->
{N, New_N2} = filter_loop_next( next(Pid1), N2, Pid1, Pid2 ),
Pid ! N
end,
filter_loop( Pid1, Pid2, New_N2 ).
 
filter_loop_next( N1, N2, Pid1, Pid2 ) when N1 > N2 -> filter_loop_next( N1, next(Pid2), Pid1, Pid2 );
filter_loop_next( N, N, Pid1, Pid2 ) -> filter_loop_next( next(Pid1), next(Pid2), Pid1, Pid2 );
filter_loop_next( N1, N2, _Pid1, _Pid2 ) -> {N1, N2}.
 
power_loop( M, N ) ->
receive {next, Pid} -> Pid ! erlang:round(math:pow(N, M) ) end,
power_loop( M, N + 1 ).
 
Output:
31> generator:task().
[529,576,625,676,784,841,900,961,1024,1089]

[edit] F#

Translation of: C#
let m n = Seq.unfold(fun i -> Some(bigint.Pow(i, n), i + 1I)) 0I
 
let squares = m 2
let cubes = m 3
 
let (--) orig veto = Seq.where(fun n -> n <> (Seq.find(fun m -> m >= n) veto)) orig
 
let ``squares without cubes`` = squares -- cubes
 
Seq.take 10 (Seq.skip 20 (``squares without cubes``))
|> Seq.toList |> printfn "%A"

Output

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


[edit] Fantom

Using closures to implement generators.

 
class Main
{
// Create and return a function which generates mth powers when called
|->Int| make_generator (Int m)
{
current := 0
return |->Int|
{
current += 1
return (current-1).pow (m)
}
}
 
|->Int| squares_without_cubes ()
{
squares := make_generator (2)
cubes := make_generator (3)
c := cubes.call
return |->Int|
{
while (true)
{
s := squares.call
while (c < s) { c = cubes.call }
if (c != s) return s
}
return 0
}
}
 
Void main ()
{
swc := squares_without_cubes ()
20.times { swc.call } // drop 20 values
10.times // display the next 10
{
echo (swc.call)
}
}
}
 

Output:

529
576
625
676
784
841
900
961
1024
1089

[edit] FunL

Translation of: Haskell
(for the powers function)
Translation of: Scala
(for the filter)
def powers( m ) = map( (^ m), 0.. )
 
def
filtered( s@sh:_, ch:ct ) | sh > ch = filtered( s, ct )
filtered( sh:st, c@ch:_ ) | sh < ch = sh # filtered( st, c )
filtered( _:st, c ) = filtered( st, c )
 
println( filtered(powers(2), powers(3)).drop(20).take(10) )
Output:
[529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

[edit] Go

Most direct and most efficient on a single core is implementing generators with closures.

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()
}

Output:

529 576 625 676 784 841 900 961 1024 1089

Alternatively, generators can be implemented in Go with goroutines and channels. There are tradeoffs however, and often one technique is a significantly better choice.

Goroutines can run concurrently, but there is overhead associated with thread scheduling and channel communication. Flow control is also different. A generator implemented as a closure is a function with a single entry point fixed at the beginning. On repeated calls, execution always starts over at the beginning and ends when a value is returned. A generator implemented as a goroutine, on the other hand, "returns" a value by sending it on a channel, and then the goroutine continues execution from that point. This allows more flexibility in structuring code.

package main
 
import (
"fmt"
"math"
)
 
func newPowGen(e float64) chan float64 {
ch := make(chan float64)
go func() {
for i := 0.; ; i++ {
ch <- math.Pow(i, e)
}
}()
return ch
}
 
// given two input channels, a and b, both known to return monotonically
// increasing values, supply on channel c values of a not returned by b.
func newMonoIncA_NotMonoIncB_Gen(a, b chan float64) chan float64 {
ch := make(chan float64)
go func() {
for va, vb := <-a, <-b; ; {
switch {
case va < vb:
ch <- va
fallthrough
case va == vb:
va = <-a
default:
vb = <-b
 
}
}
}()
return ch
}
 
func main() {
ch := newMonoIncA_NotMonoIncB_Gen(newPowGen(2), newPowGen(3))
for i := 0; i < 20; i++ {
<-ch
}
for i := 0; i < 10; i++ {
fmt.Print(<-ch, " ")
}
fmt.Println()
}

[edit] 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:

import Data.List.Ordered
 
powers m = map (^ m) [0..]
 
squares = powers 2
cubes = powers 3
foo = filter (not . has cubes) squares
 
main :: IO ()
main = print $ take 10 $ drop 20 $ foo

Sample output

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

[edit] 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.

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

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

[edit] 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:

coclass 'mthPower'
N=: 0
create=: 3 :0
M=: y
)
next=: 3 :0
n=. N
N=: N+1
n^M
)

And, here are corresponding square and cube generators

stateySquare=: 2 conew 'mthPower'
stateyCube=: 3 conew 'mthPower'

Here is a generator for squares which are not cubes:

coclass 'uncubicalSquares'
N=: 0
next=: 3 :0"0
while. (-: <.) 3 %: *: n=. N do. N=: N+1 end. N=: N+1
*: n
)

And here is an example of its use:

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

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

mthPower=: 1 :'^&m@i.'
squares=: 2 mthPower
cubes=: 3 mthPower
uncubicalSquares=: squares -. cubes

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:

uncubicalSquares=: {. squares@<.@p.~&3 1.1 -. cubes

Example use:

20 }. uncubicalSquares 30 NB. the 21st through 30th uncubical square
529 576 625 676 784 841 900 961 1024 1089

[edit] JavaScript

 
function PowersGenerator(m) {
var n=0;
while(1) {
yield Math.pow(n, m);
n += 1;
}
}
 
function FilteredGenerator(g, f){
var value = g.next();
var filter = f.next();
 
while(1) {
if( value < filter ) {
yield value;
value = g.next();
} else if ( value > filter ) {
filter = f.next();
} else {
value = g.next();
filter = f.next();
}
}
}
 
 
 
var squares = PowersGenerator(2);
var cubes = PowersGenerator(3);
 
var filtered = FilteredGenerator(squares, cubes);
 
 
 
for( var x = 0; x < 20; x++ ) filtered.next()
for( var x = 20; x < 30; x++ ) console.logfiltered.next());
 
 

[edit] Julia

The task can be achieved by using closures, iterators or tasks. Here is a solution using anonymous functions and closures.

drop(n, gen) = (for i=1:n gen() end ; gen)
 
take(n, gen) = [gen() for i=1:n]
 
pgen(n) = let x=0; () -> (x+=1)^n; end
 
function genfilter(gen1, gen2)
let r1 = -Inf, r2 = gen2()
() -> begin
r1 = gen1()
while r2 < r1 r2 = gen2() end
while r1 == r2 r1 = gen1() end
r1
end
end
end
Output:
julia> show(take(10, drop(20, genfilter(pgen(2),pgen(3)))))
{529,576,625,676,784,841,900,961,1024,1089}

[edit] Lua

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

 
--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
 

[edit] Nimrod

proc `^`*(base: int, exp: int): int =
var (base, exp) = (base, exp)
result = 1
 
while exp != 0:
if (exp and 1) != 0:
result *= base
exp = exp shr 1
base *= base
 
proc next(s): int =
for n in s(): return n
 
proc powers(m): auto =
iterator it(): int{.closure.} =
for n in 0 .. <int.high:
yield n ^ m
return it
 
iterator filtered(s1, s2): int =
var v = next(s1)
var f = next(s2)
while True:
if v > f:
f = next(s2)
continue
elif v < f:
yield v
v = next(s1)
 
var
squares = powers(2)
cubes = powers(3)
i = 1
for x in filtered(squares, cubes):
if i > 20:
echo x
if i >= 30:
break
inc i

Output:

529
576
625
676
784
841
900
961
1024
1089

[edit] Perl

These generators are anonymous subroutines, which are closures.

# gen_pow($m) creates and returns an anonymous subroutine that will
# 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; };
}
 
# gen_filter($g1, $g2) generates everything returned from $g1 that
# is not also returned from $g2. Both $g1 and $g2 must be references
# to subroutines that generate numbers in increasing order. gen_filter
# 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;
}
};
}
 
# Create generators.
my $squares = gen_pow(2);
my $cubes = gen_pow(3);
my $squares_without_cubes = gen_filter($squares, $cubes);
 
# Drop 20 values.
$squares_without_cubes->() for (1..20);
 
# Print 10 values.
my @answer;
push @answer, $squares_without_cubes->() for (1..10);
print "[", join(", ", @answer), "]\n";
Output:
[529, 576, 625, 676, 784, 841, 900, 961, 1024, 1089]

[edit] Perl 6

As with Haskell, generators are disguised as lazy lists in Perl 6.

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(', ');

Output:

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

[edit] PicoLisp

Coroutines are available only in the 64-bit version.

(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)))

Output:

529
576
625
676
784
841
900
961
1024
1089

[edit] PL/I

 
Generate: procedure options (main); /* 27 October 2013 */
declare j fixed binary;
declare r fixed binary;
 
/* Ignore the first 20 values */
do j = 1 to 20;
/* put edit (filter() ) (f(6)); */
r = filter ();
end;
put skip;
do j = 1 to 10;
put edit (filter() ) (f(6));
end;
 
/* filters out cubes from the result of the square generator. */
filter: procedure returns (fixed binary);
declare n fixed binary static initial (-0);
declare (i, j, m) fixed binary;
 
do while ('1'b);
m = squares();
r = 0;
do j = 1 to m;
if m = cubes() then go to ignore;
end;
return (m);
ignore:
end;
end filter;
 
squares: procedure returns (fixed binary);
declare i fixed binary static initial (-0);
 
i = i + 1;
return (i**2);
end squares;
 
cubes: procedure returns (fixed binary);
 
r = r + 1;
return (r**3);
end cubes;
 
end Generate;
 
20 dropped values:
     4     9    16    25    36    49    81   100   121   144   169   196   225
 256   289   324   361   400   441   484

Next 10 values:
   529   576   625   676   784   841   900   961  1024  1089

[edit] 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.

Works with: Python version 2.6+ and 3.x
(in versions prior to 2.6, replace next(something) with something.next())
from itertools import islice, count
 
def powers(m):
for n in count():
yield n ** m
 
def filtered(s1, s2):
v, f = next(s1), next(s2)
while True:
if v > f:
f = next(s2)
continue
elif v < f:
yield v
v = next(s1)
 
squares, cubes = powers(2), powers(3)
f = filtered(squares, cubes)
print(list(islice(f, 20, 30)))

Sample output

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

[edit] R

powers = function(m)
{n = -1
function()
{n <<- n + 1
n^m}}
 
noncubic.squares = local(
{squares = powers(2)
cubes = powers(3)
cube = cubes()
function()
{square = squares()
while (1)
{if (square > cube)
{cube <<- cubes()
next}
else if (square < cube)
{return(square)}
else
{square = squares()}}}})
 
for (i in 1:20)
noncubic.squares()
for (i in 1:10)
message(noncubic.squares())

[edit] Racket

 
#lang racket
 
(require racket/generator)
 
;; this is a function that returns a powers generator, not a generator
(define (powers m)
(generator ()
(for ([n (in-naturals)]) (yield (expt n m)))))
 
(define squares (powers 2))
(define cubes (powers 3))
 
;; same here
(define (filtered g1 g2)
(generator ()
(let loop ([n1 (g1)] [n2 (g2)])
(cond [(< n1 n2) (yield n1) (loop (g1) n2)]
[(> n1 n2) (loop n1 (g2))]
[else (loop (g1) (g2))]))))
 
(for/list ([x (in-producer (filtered squares cubes) (lambda (_) #f))]
[i 30] #:when (>= i 20))
x)
 

The output:

'(529 576 625 676 784 841 900 961 1024 1089)

[edit] REXX

Code was added to support listing of a specified number of values, the default is 0 (zero).
The generators lie dormant until a request is made (illustrated by the calling of "TELL" to display some values).
A lot of unnecessary iterator calls could be eliminated (and making the program a lot faster) if a check would be made to
determine if a value has been emitted (essentially, this would be using memoization and would be easy to implement).
The REXX program can handle any numbers, not just positive integers; one only need to increase the size of the DIGITS if
more digits are needed for extra-large numbers.

/*REXX program to show how to use a generator (also known as iterators).*/
numeric digits 10000 /*just in case we need big 'uns. */
parse arg show; show = word(show 0, 1) /*show this many.*/
@gen.= /*generators start from scratch. */
do j=1 to show; call tell 'squares' ,gen_squares(j)  ; end
do j=1 to show; call tell 'cubes' ,gen_cubes(j)  ; end
do j=1 to show; call tell 'sq¬cubes',gen_sqNcubes(j) ; end
if show>0 then say 'dropping 1st ──► 20th values.'
do j=1 to 20; drop @gen.sqNcubes.j  ; end
do j=20+1 for 10  ; call tell 'sq¬cubes',gen_sqNcubes(j) ; end
exit /*stick a fork in it, we're done.*/
/*─────────────────────────────────────gen_powers iterator──────────────*/
gen_powers: procedure expose @gen.; parse arg x,p; if x=='' then return
if @gen.powers.x.p=='' then @gen.powers.x.p=x**p; return @gen.powers.x.p
/*─────────────────────────────────────gen_squares iterator─────────────*/
gen_squares: procedure expose @gen.; parse arg x; if x=='' then return
if @gen.squares.x=='' then do; call gen_powers x,2
@gen.squares.x=@gen.powers.x.2
end
return @gen.squares.x
/*─────────────────────────────────────gen_cubes iterator───────────────*/
gen_cubes: procedure expose @gen.; parse arg x; if x=='' then return
if @gen.cubes.j=='' then do; call gen_powers x,3
@gen.cubes.x=@gen.powers.x.3
end
return @gen.cubes.x
/*─────────────────────────────────────gen_squares not cubes iterator───*/
gen_sqNcubes: procedure expose @gen.; parse arg x; if x=='' then return
s=0
if @gen.sqNcubes.x=='' then do j=1 to x
if @gen.sqNcubes\=='' then do; sq=sq+1
iterate
end
do s=s+1 /*slow way to weed out cubes*/
 ?=gen_squares(s)
do c=1 until gen_cubes(c)>?
if gen_cubes(c)==? then iterate s
end /*c*/
leave
end /*s*/
@gen.sqNcubes.x=?
@gen.sqNcubes.x=@gen.squares.s
end /*j*/
return @gen.sqNcubes.x
/*──────────────────────────────────TELL subroutine─────────────────────*/
tell: if j==1 then say /* [↓] format args to be aligned.*/
say right(arg(1),20) right(j,5) right(arg(2),20); return

output when using the default (no input)

            sq¬cubes    21                  529
            sq¬cubes    22                  576
            sq¬cubes    23                  625
            sq¬cubes    24                  676
            sq¬cubes    25                  784
            sq¬cubes    26                  841
            sq¬cubes    27                  900
            sq¬cubes    28                  961
            sq¬cubes    29                 1024
            sq¬cubes    30                 1089

output when using the following for input: 10

             squares     1                    1
             squares     2                    4
             squares     3                    9
             squares     4                   16
             squares     5                   25
             squares     6                   36
             squares     7                   49
             squares     8                   64
             squares     9                   81
             squares    10                  100

               cubes     1                    1
               cubes     2                    8
               cubes     3                   27
               cubes     4                   64
               cubes     5                  125
               cubes     6                  216
               cubes     7                  343
               cubes     8                  512
               cubes     9                  729
               cubes    10                 1000

            sq¬cubes     1                    4
            sq¬cubes     2                    9
            sq¬cubes     3                   16
            sq¬cubes     4                   25
            sq¬cubes     5                   36
            sq¬cubes     6                   49
            sq¬cubes     7                   81
            sq¬cubes     8                  100
            sq¬cubes     9                  121
            sq¬cubes    10                  144
dropping 1st ──► 20th values.
            sq¬cubes    21                  529
            sq¬cubes    22                  576
            sq¬cubes    23                  625
            sq¬cubes    24                  676
            sq¬cubes    25                  784
            sq¬cubes    26                  841
            sq¬cubes    27                  900
            sq¬cubes    28                  961
            sq¬cubes    29                 1024
            sq¬cubes    30                 1089

[edit] 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
# This solution cheats and uses only one generator!
 
def powers(m)
return enum_for(__method__, m) unless block_given?
 
n = 0
loop { yield n ** m; n += 1 }
end
 
def squares_without_cubes
return enum_for(__method__) unless block_given?
 
cubes = powers(3)
c = cubes.next
powers(2) do |s|
c = cubes.next while c < s
yield s unless c == s
end
end
 
p squares_without_cubes.take(30).drop(20)
# p squares_without_cubes.lazy.drop(20).first(10) # Ruby 2.0+
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
# This solution uses three generators.
 
def powers(m)
return enum_for(__method__, m) unless block_given?
 
n = 0
loop { yield n ** m; n += 1 }
end
 
def squares_without_cubes
return enum_for(__method__) unless block_given?
 
cubes = powers(3)
c = cubes.next
squares = powers(2)
loop do
s = squares.next
c = cubes.next while c < s
yield s unless c == s
end
end
 
answer = squares_without_cubes
20.times { answer.next }
p 10.times.map { answer.next }
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.


The other way. Powers method is the same as the above.

Translation of: Python
def filtered(s1, s2)
return enum_for(__method__, s1, s2) unless block_given?
v, f = s1.next, s2.next
loop do
v > f and f = s2.next and next
v < f and yield v
v = s1.next
end
end
 
squares, cubes = powers(2), powers(3)
f = filtered(squares, cubes)
p f.take(30).last(10)
# p f.lazy.drop(20).first(10) # Ruby 2.0+

Output is the same as the above.

[edit] Scala

object Generators {
def main(args: Array[String]): Unit = {
def squares(n:Int=0):Stream[Int]=(n*n) #:: squares(n+1)
def cubes(n:Int=0):Stream[Int]=(n*n*n) #:: cubes(n+1)
 
def filtered(s:Stream[Int], c:Stream[Int]):Stream[Int]={
if(s.head>c.head) filtered(s, c.tail)
else if(s.head<c.head) Stream.cons(s.head, filtered(s.tail, c))
else filtered(s.tail, c)
}
 
filtered(squares(), cubes()) drop 20 take 10 print
}
}

Here is an alternative filter implementation using pattern matching.

def filtered2(s:Stream[Int], c:Stream[Int]):Stream[Int]=(s, c) match {
case (sh#::_, ch#::ct) if (sh>ch) => filtered2(s, ct)
case (sh#::st, ch#::_) if (sh<ch) => sh #:: filtered2(st, c)
case (_#::st, _) => filtered2(st, c)
}

Output:

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

[edit] Scheme

(define (power-seq n)
(let ((i 0))
(lambda ()
(set! i (+ 1 i))
(expt i n))))
 
(define (filter-seq m n)
(let* ((s1 (power-seq m)) (s2 (power-seq n))
(a 0) (b 0))
(lambda ()
(set! a (s1))
(let loop ()
(if (>= a b) (begin
(cond ((> a b) (set! b (s2)))
((= a b) (set! a (s1))))
(loop))))
a)))
 
(let loop ((seq (filter-seq 2 3)) (i 0))
(if (< i 30)
(begin
(if (> i 20)
(begin
(display (seq))
(newline))
(seq))
(loop seq (+ 1 i)))))
output
576
625
676
784
841
900
961
1024
1089

[edit] 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.

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
 
# Drop 20
for {set i 0} {$i<20} {incr i} {filtered}
# Take/print 10
for {} {$i<30} {incr i} {
puts [filtered]
}

Output:

529
576
625
676
784
841
900
961
1024
1089

[edit] XPL0

code ChOut=8, IntOut=11;
 
func Gen(M); \Generate Mth powers of positive integers
int M;
int N, R, I;
[N:= [0, 0, 0, 0]; \provides own/static variables
R:= 1;
for I:= 1 to M do R:= R*N(M);
N(M):= N(M)+1;
return R;
];
 
func Filter; \Generate squares of positive integers that aren't cubes
int S, C;
[C:= [0]; \static variable = smallest cube > current square
repeat S:= Gen(2);
while S > C(0) do C(0):= Gen(3);
until S # C(0);
return S;
];
 
int I;
[for I:= 1 to 20 do Filter; \drop first 20 values
for I:= 1 to 10 do [IntOut(0, Filter); ChOut(0, ^ )]; \show next 10 values
]
Output:
529 576 625 676 784 841 900 961 1024 1089 

[edit] zkl

Translation of: Python

Generators are implemented with fibers (aka VMs) and return [lazy] iterators.

fcn powers(m){ n:=0.0; while(1){vm.yield(n.pow(m).toInt()); n+=1} }
var squared=Utils.Generator(powers,2), cubed=Utils.Generator(powers,3);
 
fcn filtered(sg,cg){s:=sg.next(); c:=cg.next();
while(1){
if(s>c){c=cg.next(); continue;}
else if(s<c) vm.yield(s);
s=sg.next()
}
}
var f=Utils.Generator(filtered,squared,cubed);
f.drop(20);
f.walk(10).println();
Output:
L(529,576,625,676,784,841,900,961,1024,1089)

For this task, generators are overkill and overweight, and lazy infinite squences can be used. There is no real change to change to the algorithms (since generators are lazy sequences), it just has been rewritten in a more functional style.

Translation of: Clojure
fcn powers(m){[0.0..].tweak(fcn(n,m){a:=n; do(m-1){a*=n} a}.fp1(m))}
var squared=powers(2), cubed=powers(3);
 
fcn filtered(sg,cg){s:=sg.peek(); c:=cg.peek();
if(s==c){ cg.next(); sg.next(); return(self.fcn(sg,cg)) }
if(s>c) { cg.next(); return(self.fcn(sg,cg)); }
sg.next(); return(s);
}
var f=[0..].tweak(filtered.fp(squared,cubed))
f.drop(20).walk(10).println();
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox