4 ms·

A self-reference object in Python for recursive calls in lambda expressions

10 points by baruchel 11y ago

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 ago
  Given 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 ago
    I'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 ago
  Thanks. Will add to my personal lua library.
- baruchel 11y ago
  Thank 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
deleted 11y ago
[deleted]
resiros 11y ago
Cool tricks. This lead me to read about the subject of frames in python (http://farmdev.com/src/secrets/framehack/index.html http://farmdev.com/src/secrets/framehack/index.html). Can anybody suggest advanced Python books to dig out more in such matters?
- davesque 11y ago
  Not trying to be snarky. Reading the official python documentation as though it were a book can lead to a lot of insights: https://docs.python.org/3/ https://docs.python.org/3/

10 points by baruchel 11y ago

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 ago
Given 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 ago
  I'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 ago
Thanks. Will add to my personal lua library.
baruchel 11y ago
Thank 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

deleted 11y ago

[deleted]

resiros 11y ago

Cool tricks. This lead me to read about the subject of frames in python (http://farmdev.com/src/secrets/framehack/index.html http://farmdev.com/src/secrets/framehack/index.html). Can anybody suggest advanced Python books to dig out more in such matters?

davesque 11y ago
Not trying to be snarky. Reading the official python documentation as though it were a book can lead to a lot of insights: https://docs.python.org/3/ https://docs.python.org/3/