5 ms·
A fixed-point combinator would work just as well here (with the added bonus of not reaching around and digging in Python internals) :) def fix(g): retu
by rfw 11y ago
A fixed-point combinator would work just as well here (with the added bonus of not reaching around and digging in Python internals) :)
def fix(g):
return (lambda f: g(lambda *args, **kwargs: f(f)(*args, **kwargs)))(
lambda f: g(lambda *args, **kwargs: f(f)(*args, **kwargs)))
Then:
fac = fix(lambda self: lambda n: 1 if n <= 1 else n*self(n-1))
For the second example:
fac2 = fix(lambda self: lambda n: 1 if n <= 1 else n*((lambda k: self(k-1))(n)))
- anon4 11y agoGiven that Python has no tail-recursion optimisation, you really shouldn't be writing functions in this style to begin with. If you really want to though, I think there is a way to make the fixed-point combinator also mess with the function internals and make the tail-call into a loop.
- boomlinde 11y agoI'd say that this depends very much on the problem. There are problems that are more elegantly and intuitively solved recursively without necessarily ascending very far on the, e.g. parsers for nested-but-not-terribly-so data, say some applications of S-expressions or a protocol like DHCPv6, or traversal of tree structures known not to be tall.
- meric 11y agoThanks. Will add to my personal lua library.
- baruchel 11y agoThank you for your comments. I am aware of the Y combinator which I played with in other modules: (see my blog: http://baruchel.github.io/blog/ http://baruchel.github.io/blog/ ) but this one was for reaching a very simple syntax for the end-user! I have a more serious module implementing tail-calls (either for recursion or not) where the end-user has to follow the syntax of the Y-combinator: see https://news.ycombinator.com/item?id=9901309 https://news.ycombinator.com/item?id=9901309