4 ms·
Very nice, this seems like it might be my first successful attempt at understanding the importance of the Y combinator. Question: As an example of the power of
by andreyf 17y ago
Very nice, this seems like it might be my first successful attempt at understanding the importance of the Y combinator. Question:
As an example of the power of this approach, this caching turns the naive, exponential implementation of Fibonacci into the optimized, linear-time version
What role does the YC play in this? Is it not simply due to memoization? Does the Y-combinator version grow the stack?
- fadmmatt 17y agoThe role the YC plays in this case is hiding the memoization. The memoizing Y combinator is the same as the Y combinator, except it doesn't re-compute inputs it's already seen. Writing recursive functions in "Y-combinator style" is a way to expose internal recursive call sites to external inspection and manipulation. The Y combinator version still grows the stack.