No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators

No Let, No Rec, No Problem: A Gentler Introduction to the Y and Z Combinators(irfanali.org)

40 points by sayyadirfanali 3 days ago | 7 comments

Trung0246 4 hours ago |

Here's a funny Z combinator in typescript in pure SKI form for lambda calculus purist:

    const K = <A, B>(a: A) => (_b: B) => a;

    const S = <A, B, C>(a: (x: C) => (y: B) => A) => (b: (x: C) => B) => (c: C) => a(c)(b(c));

    const Z = S(K(S(S(K)(K))(S(K)(K))))(S(S(K(S))(K))(K(S(K(S(S)(S(K))))(S(S(K(S))(K))(K)))));

https://en.wikipedia.org/wiki/Fixed-point_combinator

p4bl0 4 hours ago |

I feel like introducing lambda calculus (using JS syntax) would be less cumbersome and convoluted than referring to "the challenge" without really justifying it and deferring to respect the rules for so long. But maybe some people entirely unfamiliar with these concepts find this approach easier?

the_other 3 hours ago | |

I found it extremely confusing.

It sets a challenge as a rhetorical tool, but then completely fails to honour the challenge through the bulk of the explanation.

- don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion

- don’t use declaration: ignoring that defining arguments to a function is declaration

I’m not saying the article is “wrong”. But I thunk I’d have preferred a plain intro to lambda calculus.

(Writing this as someone who has struggled to learn “real” functional programming the few times I’ve tried over the past 20+ years, but who very much likes using RxJS and the functional flavour of lodash and wishes I could see deeper into that black hole.)

mrkeen 2 hours ago | | |

> don’t use recursion: spends multiple paragraphs implying that a function calling itself isn’t recursion

It did the opposite. It wrote many paragraphs of code and threw each one out as soon as recursion showed up.

p4bl0 2 hours ago | | |

So it's as confusing as I thought to do it that way. I wasn't sure if I thought so because I'm already familiar with all these concepts or because this introduction is indeed convoluted. Thanks for taking the time to reply!

biorach 1 hour ago | |

I found this to be the most accessible introduction to the Y combinator I've yet read.

satvikpendem 4 hours ago |

Good to see this in the second chance pool. Unfortunately I don't think most commenters know what the article is about and thus we may end up with this submission leaving the front page quickly, a shame though as the YC namesake is from similar articles as these, a company that produces other companies, as Paul Graham had said.

const K = <A, B>(a: A) => (_b: B) => a; const S = <A, B, C>(a: (x: C) => (y: B) => A) => (b: (x: C) => B) => (c: C) => a(c)(b(c)); const Z = S(K(S(S(K)(K))(S(K)(K))))(S(S(K(S))(K))(K(S(K(S(S)(S(K))))(S(S(K(S))(K))(K)))));