Flurry

« first day (53 days earlier) ← previous day next day → last day (41 days later) »

Esolanging Fruit

06:41

You can use the delayed application combinator to implement a Y combinator:

fix = λf. (λx. x x) (λx. f (D x x))
    = (λx. x x) ∘ (λf x. f (D x x))
    = (λx. x x) ∘ (λf. f ∘ (λx. D x x))
    = S I I ∘ (λf. f ∘ S D I)
   := <[<>{{}}{{}}]{<{}[<>{<><<>[<>[(){}]]()>[(){{}}]}{{}}]>}>

(haven't tested if it works, but it should in principle)

Actually, there's an alternative derivation of D for when f and a are already known:

D f a = S (S (K f) (K a)) I
     := <> <f [() a]> {{}}

Esolanging Fruit

07:02

That gives us a much shorter derivation:

fix = λf. (λx. f (D x x)) (λx. f (D x x))
    = λf. push (λx. f (D x x)) pop
    = λf. push (f ∘ λx. D x x) pop
    = λf. push (f ∘ λx. S (S (K x) (K x))) pop
    = λf. push (f ∘ S ∘ λx. S (K x) (K x)) pop
    = λf. push (f ∘ S ∘ λx. (S ∘ K) x (K x)) pop
    = λf. push (f ∘ S ∘ S (S ∘ K) K) pop
   := {(<{}<>[<><<>()>()]>){}}

Esolanging Fruit

07:17

Noticing <><<>()> in the expression prompted me to try a few iterates of succ at K:

succ K = (λn f x. f (n f x)) K
       = λf x. f (K f x)
       = λf x. f f
       = λf x. f f

succ (succ K) = (λn f x. f (n f x)) (λf x. f f)
              = λf x. f ((λf x. f f) f x)
              = λf x. f (f f)

and more generally, succⁿ K = λf x. fⁿ f

where fⁿ represents function iteration

Esolanging Fruit

07:36

In practice, if you want to write a recursive function S S K = λa b. a b a might be a more useful combinator than fix.

For example, with P = S S K you can implement factorial along the lines of P (λn s. if n = 0 then 1 else P s (n - 1))