9
3
Write a fixed point combinator in as few characters as possible, in the language of your choice.
- free form (i.e., whatever's shortest): whole program, actual function, code snippet
- you may not use your standard library's if it has one
- you may however extract it from other high-level functions it you'd rather do that than construct it from the bases
Please include a recursive factorial or Fibonacci that uses it as a demo.
In this question, self-reference is acceptable, the aim is solely to remove it from the recursive function it will apply to.
Is a lazy-language implementation ok? (Would you accept
(define Y(lambda(f)(f(Y f))))
?) – Eelvex – 2011-02-19T20:28:44.843Any implementation you can demonstrate with one of the requested examples is ok. – J B – 2011-02-19T21:52:40.547
1If I'm not mistaken, strictly speaking, the term "Y combinator" refers specifically to a single fixpoint combinator discovered by Haskell Curry, λf.(λx.f (x x)) (λx.f (x x)) . – Joey Adams – 2011-02-20T01:32:49.400
@Eelvex: Obviously both answers so far (including the OP's own answer) use the cheating way, so, I guess that makes it okay. :-P Personally, I'd rather go with @Joey's approach and say that only the real (non-self-referential) Y combinator will do. ;-) – Chris Jester-Young – 2011-02-20T02:21:09.093
@Chris: Oh my. That's what I had in mind initially, and then I... forgot along the way. It's kind of too late to change now, we'll have to open another question. – J B – 2011-02-20T11:06:52.487