3 ms·
On the functional side of things you can get by with just the two combinators S and K: http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia
by arethuza 15y ago
On the functional side of things you can get by with just the two combinators S and K:
http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus
You can define the Y combinator, and therefore recursion quite happily (if not very efficiently) using S and K.
I believe there are also approaches that use as single universal combinator - but I can't find any good references to these - I'd be quite interested to see definitions of S and K in terms of a single universal combinator.
- 0x12 15y agohttp://en.wikipedia.org/wiki/Iota_and_Jot http://en.wikipedia.org/wiki/Iota_and_Jot <- that one?
- arethuza 15y agoI thought that definition looked a bit like cheating - wrapping up S & K in a form that makes it straightforward to get back to them! There is also a U combinator referenced on this page: http://www.ucombinator.org/ http://www.ucombinator.org/ as U = λ f . f(f) - haven't had time to sit down and actually work it through though. [Edit: I notice that page says that U enables universal computation, not that it is sufficient.]
- 0x12 15y agoYes, I agree it is a bit cheating. They recover the S and K by applying U to itself in interesting ways, but that's like saying 'this tool is so universal, you can use it as a hammer and a chisel by banging one instance of the tool with another tool just like it'. That's not a very mathematical way of putting it I guess but I believe that is more or less the spirit of it.