Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

It's an example of Combinatory Logic. For another example check out SKI combinators. SKI is actually kind of close to this but using three combinators instead of one it's a bit simpler to understand (IMO).

https://en.wikipedia.org/wiki/Combinatory_logic

https://en.wikipedia.org/wiki/SKI_combinator_calculus



Note that the I combinator is redundant since `I = SK`, so all we really need is `SK`. There are alternatives like Iota with a single combinator, but they're essentially an obfuscated mix of S and K; so it's usually clearer to stick with SK.

Note that the first two rules of this Tree Calculus are precisely those of K and S.


> I = SK

Wrong. I = S K M where M can be anything:

    I x = S K M x = K x (M x) = x
K and S K represent True and False, since K x y = x and S K x y = y.

> essentially an obfuscated mix of S and K

Most alternatives are tuples of S and K like λz. z S K or λz. z K S K. But the arguably shortest one is indeed a proper mix:

    A = λx λy λz. x z (y (λ. z)) = λx λy λz. x z (y (K z))


Oops, sorry; I got part way through writing I = S K K, but went off to another tab to double-check, and forgot to update that expression when I came back!

You're absolutely right.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: