I love Twenty Six Beaches, which
comes from the time when I numbered every riff that I had written. I had fun
adding a drum track and remixing the melody!
Then there’s Captain Jack which originally came
from a riff I wrote during my emo phase. Credit to @Jeff for jamming with me
on this riff many times and coming up with lyrics.
Pymbda is a library that I wrote which turns a few Python statements into
functions. It’s not quite Hylang, but it’s as functional as Python can be.
Right now there are four functions: if_, ifelse,
tryexcept, and with_
if_ takes a predicate function or an object as its first parameter, and will
either evaluate the function or check the truthiness of the first parameter. if
true it will execute the second parameter as a function.
yield from is a powerful feature of Python 3 that allows for recursion with
generators. when a function has a yield statement, it ends up returning a
generator. If your intention is to have a recursive algorithm and have all
calculated values pass through to the original caller as a single generator (for
debugging, or to produce a sequence of numbers)
regardless of which recursive call the value was created by, then using a simple
yield won’t work.
As an example, here’s a factorial yield that might seem like it would work.
The expected output is a generator that produces the factorials from 1 to n.
What’s happening here is that factorial(i) calls factorial(i-1), which produces
a generator that yields factorial(i-1) then returns factorial(i-1). We can’t
multiply n by the generator, so we would need to fix this example, in a
cringeworthy way, like the following:
deffactorial(n):ifn==1:yield1return1else:#we know factorial(n-1) has len(1) so we can do thisgenerator=list(factorial(n-1))x=n*generator[0]yieldxreturnxprint(list(factorial(3)))[6]
The intention here is to get rid of the int * generator warning. We returned
the final value from the function call in a generator (because that’s how we
defined the function), but we’re missing out on the original intention of the
exercise. An issue with this approach is that it would require the generator to
have length of 1, which may not always be the case.
This leads us back to the original question posed at the beginning of the
article.
How do I seemlessly pass all intermediary values to the original caller that
are produced by a recursive function? Enter yield from
The only difference in this example is the addition of the yield from statement. yield from allows the values yielded in factorial(n-1) to be yielded in factorial(n), which would be received in factorial(n+1)’s yield from statement, or would be passed along to the original caller.
The reason why there are return statements is because in this example, yield from is serving two purposes. It’s yield values from factorial(n-1) but it’s also returning factorial(n-1). Now the yield values can’t be used inside any factorial calls, they’re purely for creating a generator to return the values to the original caller of factorial(n), and the return statements are for calculating the factorial inside the recursive call chain.
Here’s a non-cached version of the fibonacci numbers.
This fibonacci example (python 3.4) produces a generator which yields every fibonacci number generated by the algorithm. Recall that a naive recursive
fibonacci algorithm will produce an exponentially large function calls.
This example shows all of the redunant calls.
Calculating fib(3) requires fib(2) + fib(1), fib(4) requires fib(3) + fib(2), etc, and this example does an increasingly large amount of work for each increasing fibonacci number. The natural way to speed this up is to cache previously calculated values. Instead of calculating fib(5) by running fib(4) + fib(3) and doing the work to calculate each one separately, a cache already knows fib(4) and fib(3), so fib(5) is equal to those cached values and the only work required is a table lookup and an addition.
If we add a cache for the fibonacci numbers then the speedup of the improved algorithm will be transparent.
Now that we added a cache, you can see that we minimize the calls to our function. If you want to see cache hits, add a yield cache[n] after the if statement but before the return in the cache.