Tree Calculus - Hackdot

Re:Tree Calculus by chriswarbo on Tuesday December 10, 2024 @12:11PM (#42378785)

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.

[ Parent | on HN ]

Re:Tree Calculus by tromp on Wednesday December 11, 2024 @04:48AM (#42386300)

> 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))

[ Parent | on HN ]

Re:Tree Calculus by chriswarbo on Wednesday December 11, 2024 @07:39AM (#42387148)

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.

[ Parent | on HN ]