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.

See also:

• http://en.wikipedia.org/wiki/Generator_(computer_science)

Task: Write a generator (or generators), in the most natural way in your language, that produces the numbers that are squares ($n^{2}$) but not cubes ($m^{3}$) and use that to print the first 21st to 30th members of that sequence.

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

The most natural way to accomplish this task in J is by not using a generator:

<lang j> 10{.20}.(^&2 -. ^&3) i.100 529 576 625 676 784 841 900 961 1024 1089</lang>

This is considerably simpler, and faster, and arguably easier to reason about, than the generator implementation.

That said, here is an implementation of a generator:

<lang j>coclass 'generator'

n=:0

next=:3 :0

 while.-. ((-: <.&.(^&1r2)) *. -.@(-: <.&.(^&1r3)))n do.
   n=: n+1
 end.
 _1 + n=:n+1

)</lang>

And, here is an example of using that generator to accomplish this task:

<lang j> 20 }.next__g"0 i.30 [ g=: conew'generator' 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]

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