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.

Free Idea – Web Pipes

The idea is to create a platform which does two things:

1. Gives developers a simple way to make money from their APIs
2. Allows users to combine APIs in a chainable pipes style

An example API is Akismet – you give them some text and they tell you if they think it is spam.

This could be a very useful service for API developers, as it allows them to ignore the annoying payment part, and concentrate on the service.

Moreover, it means payment is abstracted for API users, so they don’t have to worry about interacting with various different providers – and payments can be payed in aggregate, so it works out nicely for smaller scale users also.

It could make web development much, much easier – since lots of tedious tasks can be removed from your app, and performed by someone who specialises in that task.

The app could be bootstrapped by making some simple, modular functions to kick things off and get people using it – but the real value is in combining APIs people come up with. You can imagine the possibilities.

Some other example APIs: file conversion, file storage, supply stock market or other data, check if links are alive or dead, spellchecking… the list is endless. There are probably already quite a few services who would be rather pleased with an opportunity like this.

Its not a new idea, but the key is building a solid platform and ecosystem around the service. The web is ready and waiting, who will be first to meet the need?

P.S. You can get all semanticy/rdfy if you like, but thats not very useful just yet :P