Hacker News Reader

Comment by leethomp | Hacker News Reader

Many primitives in array languages match the behaviour of certain combinators in combinatory logic. The page shows (left to right) the symbol for a certain combinator, its effective operation in APL syntax where x and y are left and right arguments (APL operators are either infix or single-parameter prefix) and F and G are similarly left and right function arguments, the 'bird' is a sort of colloquial name for a particular combinator, 'TinyAPL' is the operator that matches the combinator in the author's APL implementation, and the diagram is a way of explaining how the combinator works visually

BQN, another array language has a page of documentation describing the same concept for their language with a bit more explanation for the combinator newcomer: https://mlochbaum.github.io/BQN/tutorial/combinator.html

View on HN

Reasonably certain the practice of naming combinators after birds comes from “To mock a mockingbird” by Raymond Smullyan. Don’t have the book on hand to verify but figured I’d drop it here because it’s a great bunch of logical puzzles

As it says in the footnote of TFA.

Can we solve for x and y? All I see is algebra here, is my intuition wrong?

It's more like a recipe (for functions).

The first example, I, is an identity function. It takes y and returns y.

The second, K, is a constant which takes X and y and returns x.

This gets more complicated as you go along. The idea is that you get rid of a lot of the syntax for composition and have it all be implicit by what you put next to each other (given APL programs are usually one long line of a bunch of different symbols all representing functions).

The intuition here is that combinators are higher order functions which take functions and combine them together in various ways. So for a simple example "fix" is a combinator in regular maths where

Fix f = {f(x): f(x) = x for all x in the domain of f}

So if f is a function or a group action or whatever, the fixed-point set of f is all points x in the domain of f such that f(x)=x. ie the points which are unchanged by x. So if f is a reflection, the points which sit on the axis of reflection.

The fixed-point combinator is of particular relevance to this site because it's often called the y combinator.

No one who would ask that question would be able to understand your answer.

Hehe. Sorry. Yes perhaps you’re right. Wasn’t trying to be obtuse but I didn’t express that particularly clearly.

Your explanation was several years worth of math studies beyond what GP was asking.

Perfectly clearly, just for a different audience.

I’m going to frame this comment.

Combinators can be a bit sill for values. The usefulness come when you use them as a meta language for functions.

More directly than the other comments: No you can’t solve for x and y here and yes your intuition is wrong.

These are functions. I don’t know your level of knowledge in math or programming and what that would mean to you. Here’s an example.

double(x) -> x*2

So, double(3) = 6. You can’t solve for x because x doesn't have a value. It’s a placeholder for whatever you put in.

These combinators are functions that take other functions and return them unmodified. “Unmodified” is a little misleading because it can do things like drop inputs.

Reply on news.ycombinator.com