How I finally understood the Y Combinator (and blew my damn mind)

Having learnt programming mostly in Python, I’ve long wondered what it is the Lisp and Haskell people yabber about so intriguingly in my favorite forums. This path lead me to finally get why they yabber so much, in five easy steps.

1. Figured it’s about time to learn Haskell, and turned to the excellent introduction Learn You A Haskell For Great Good. Read up until the chapter on recursion, and began to understand the fundmental distinction between functional programming and imperative style:

“you do computations in Haskell by declaring what something is instead of declaring how you get it”

[mind status: mildly blown]

2. Got to the chapter on higher order functions and discovered the notion of function composition (aka point-free programming). Decided that was kinda cool.

[mind status: moderately blown]

3. Wondered about johnnowak’s reddit comment wanting to see emphasis on point-free programming in a new programming language; what is so great about writing programs by composing functions? Followed his link to tacit programming (another name for point-free style).

Noticed that combinators/combinatory logic seem important to point-free style, and remembered that the language factor seems to do a lot of this, and that it looks pretty cool.

[mind status: bordering on blown]

4. Learnt about combinatory logic, to the point where the language unlambda, astonishingly, actually seemed to make sense.

[mind status: blown]

5. From combinatory logic, followed a link to fixed point combinator, of which the most famous is the Y combinator (which allows the definition of anonymous recursive functions). Read, re-read (including relevant links), re-re-read very slowly…

And that is the story of how I blew my damn mind.

Looking forward to finally start going through SICP and Real World Haskell.

Update: some comments on hacker news question the practical usefulness of understanding the Y combinator.

What blew my mind is how it forces an appreciation for the nature and power of thinking functionally. Getting a feel for function composition, combinators and lambda calculus opens the door to a very different approach for creating programs. A good introduction to why thinking functionally may be is useful is Functional Programming For The Rest of Us.  Also Raganwald’s discussion of a classic functional programming paper,  Why Functional Programming Matters.

Also, the Y combinator itself is very shiny.


10 Responses to “How I finally understood the Y Combinator (and blew my damn mind)”

  1. 1 Avinash Meetoo April 28, 2009 at 9:11 am

    Nice post!

    I’ve been trying to understand the Y combinator for some years at least but it’s always the same. Things start well enough and then I find myself reading the bloody book or paper on autopilot mode after some time, uttering all the words written but not understanding anything :-)

    I’ll fight with it again today. I promise.

    • 2 noeit April 28, 2009 at 12:57 pm

      My experience has been similar, it has taunted me for some time. I think it clicked this time since I’ve been reading-around functional programming and combinators in bits and pieces, and finally put it all together.

      I can also stongly recommend Micheal Vanier’s very direct and clear explanation, below.

  2. 3 Michael Vanier April 28, 2009 at 10:24 am

    Might I humbly suggest my own offering:

  3. 6 chucke99 April 29, 2009 at 5:22 am

    I followed a link from WordPress’s “fastest growing blogs” to find your post on Y combinators and Haskit whatevers. I’m not a programmer, so don’t understand any of it, but your post made me wish I did. Someday maybe…

  4. 8 Hadoduefeve December 10, 2009 at 5:21 pm

    Phat article, amazing looking website, added it to my favorites!

  5. 9 April 30, 2014 at 11:18 am

    Hi there tߋ all, it’s trulƴ a good fօг me to visit this web site, it consists of useful Iոformation.

  6. 10 Johnd735 May 30, 2014 at 5:49 pm

    Nice site. On your blogs extremely interest and i will tell a buddies. fgggdafakeef

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: