Generator/Exponential
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
- 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).
- Use it to create a generator of:
- Squares.
- Cubes.
- Create a new generator that filters all cubes from the generator of squares.
- 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
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>
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]
Tcl
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
- Drop 20
for {set i 0} {$i<20} {incr i} {filtered}
- Take/print 10
for {} {$i<30} {incr i} {
puts [filtered]
}</lang> Output:
529 576 625 676 784 841 900 961 1024 1089