Common combinators in JavaScript | Hacker News Reader

Common combinators in JavaScript

gist.github.com

160 pointsjxub49 comments

This site embodies everything I dislike about functional programming: an attitude that shorter and less specific is better.

What use is a line like

    const S = f => g => x => f(x)(g(x));

for anyone except someone who already groks what the S combinator does and is for?

Why do these combinators have single-letter names anyway? Does that help anyone? Even Haskell, heaven on earth for single-letter guess-what-i-mean coders, has actual names for half of these - how is knowing that "flip" is also "the C combinator" helpful in any way?

Now, I'm not trying to diss this page in particular, and I very much am not trying to diss functional programming. I like functional programming. But I think that when hype shifted from OOP to FP, we threw half the baby out with the bathwater (ok, maybe a quarter baby). Naming is important and FP does not have any feature in particular that makes "I" a better name than "identity".

I think programming in general, and FP in particular, will become a better place if we all grow up a bit and stop pretending we're too smart to need good naming.

This is an implementation of combinatory logic and nothing to do with functional programming.

https://en.wikipedia.org/wiki/Combinatory_logic

the term functional programming has taken to mean more than just programming with functions. combinator logic certainly counts

For perspective: this is maths, not programming. You learn about these combinators in your typical lambda calculus course at uni.

It's a fun POC to actually represent it in code, not a serious proposal for production grade software.

Why do equations use single-letter variables? Or those weird greek symbols? Because they are concise, and their use is so localized that you don't need long names to keep track of them.

I agree, and I think the use of single letters is appropriate here, but "concise" is not a good enough reason to use short variable names when you're writing code for other people to consume.

In this case, I'd say it's not about being concise, but rather matching the mathematical notation that people are used to seeing when studying these combinators.

No one would implement this in a real productive project. This is for explanatory reasons only, and aimed at people already familiar with combinatorial logic.

>> I think programming in general, and FP in particular, will become a better place if we all grow up a bit and stop pretending we're too smart to need good naming.

I with you on this, but I think this is a bad example.

And while we are at it, documentation matters as well. The 'good code is the best documentation' attitude[ * ] might be valid if your methods consist of 3 lines and you use 6 methods in 5 modules. But anything bigger will become hard to maintain in the long run.

[ * ]: I encountered this especially in the haskell and erlang world.

> No one would implement this in a real productive project.

Oh my word. If it's code on the internet someone will use it. Especially functional programmers who have somehow landed themselves in a JavaScript position. I've seen much stranger code pulled off the internet and used in production applications by professionals.

That's why it's important to generally publish the best code possible whenever we can.

> Especially functional programmers who have somehow landed themselves in a JavaScript position.

Or Haskell programmers who have somehow landed themselves in any position. I've seen Haskell implemented in Erlang :)

Ehhhh, I hate reading this kind of comment. Can I suggest try to be more humble and read more before having an opinion on something?

You’re going to get downvotes to hell because of the tone of this (and that’s probably fair) but you raise a good point: that form IS extremely common in basically all technical books. It’s probably more common that O notation.

The comment makes poster look like they haven’t read anything CompSci related.

This comment breaks the guidelines. Please don't post like this.

https://news.ycombinator.com/newsguidelines.html

Same reason we use + instead of Math.addTwoIntegers(). Pure snobbery.

However, we don't combine + with other operators to form an illegible mess.

Even ++ is frowned upon for being unreadable/easily missed and/or placed in the wrong spot.

`5 + 10 * 2`?

Not sure I see your point.

They’re just standard “ignore the name this is about how things are combined” notation.

It’s algebra but with functions.

If you read any computer science books they’ll often use this form. It’s a holdover from mathematical notation.

"What use is <symbols> for anyone except someone who already groks what the S combinator does and is for?"

How does this not apply to any and all identifiers and symbols and functions?

What use is a given function until you read its signature, implementation, and docstring?

You could use this to condemn all abstraction. After all, even a function you take for granted comes at the expense of indirection.

It just so happens that we as craftsmen make trade-offs. Imagine a pattern that shows up so much that you can extract it into a function like a combinator. For instance, look at parser combinators. Yes, you'd have to credentialize in some patterns, but once again, that's what we do every day as we work on what amount to machinas of abstraction.

What use is Chinese for someone who doesn't read Chinese? The S combinator written like that is perfectly legible and fine for someone who is already familiar with the S Combinator. I don't see the problem there and I don't already grok the S Combinator. I do appreciate writing code under the assumption people working on the code would have some level of prerequisite knowledge.

I'm sure you'd get a kick out of Co-dfns [0]. But once you learn to "speak" APL programming it makes a lot more sense. I'd highly recommend, if you have the time, to listen to the author explaining the code for the compiler [1].

[0] https://github.com/Co-dfns/Co-dfns/blob/master/codfns.pdf

[1] https://www.youtube.com/watch?v=gcUWTa16Jc0 / HN discussion: https://news.ycombinator.com/item?id=13638086

Standard names are good names.

That said, Math is very contextual while development has many varying scope levels. Single letters identifiers are normally not a good choice in a global context because of collisions, however good names they may be.

I think you've interpreted this as meant to be useful tool for programmer -- and there your criticisms would be spot on. However, this is more of an interesting note for mathematicians than anything else.

I agree with your gripe.

We are in a field where backgrounds vary widely.

A little "what am I looking at and why do I care" would be useful on this page.

const S = f => g => x => f(x)(g(x));

I'm more likely to write

    const geed = g(x);
    const effed = f(x);
    const S = effed(geed);

I have no idea when I would actually write a structure like this though. Can someone please fill those names in with something like `buildComparator` or `Math.max.apply` or something, anything, that remotely makes sense?

You'd use something like this when `f` and `g` are also parameters to your function.

  some_function(f, g, x) {
    var effed = f(x);
    var geed = g(x);
    var S = effed(geed);
    // some other logic
  }

Not the S combinator, but consider being able to pass a comparator function to your sort function in C. Or passing an arbitrary predicate to `filter` or an arbitrary binary function/operator to `fold`. The S combinator itself may not be that useful, but higher order functions in general are very useful.

You'll also see their utility if you use tacit programming (programming without variables). Again, maybe not the explicit combinators listed here, but the mode of operating is the same. Tacit programming is easily explored through J, APL (less accessible due to the character set), the various MLs and Haskell.

It's one of those things that you arrive at yourself. You rarely, if ever, understand them from Haskell-ish mathematical-ish constructs like these.

Sometimes you could end up with this code in situations like this:

   const data = getDataForUser(user);
   const transformer = getTransformersForGDPR();
   const sanitizedData = transformer(data);

where getTransformersForGDPR returns a single function that may contain a chain of data transformations.

The example is contrived, of course, but you do end up with similar constructs especially if you have been exposed to functional programming.

Ah, that does make sense. I think this happens in the React world sometimes, where a single state holds the source of truth for everything, and we end up passing parts of it around to other methods to make decisions.

   const data = getDataFromState(state);
   const transformer = getTransformersForState(state);
   const sanitizedData = transformer(data);

It looks like something you’d do when the function args are the wrong way around and you rely on currying, and you don’t have a clojure style ‘thread-last’ operator.

Combinators aren't just programming, they're primarily mathematics. If you think mathematical notation needs to be more verbose, say that, but at least have some idea of what you're saying before you try to dump this supposed problem on a different field.

That's why this exists: https://github.com/hemanth/functional-programming-jargon

Your comment reminded me one of the essays of PG. http://paulgraham.com/power.html Although I agree with you in general, I think it actually can make us smarter if some piece of code requires us to think on it to internalize.

This is why I don't like math. I guess mathematicians write like that because it's faster to write on a blackboard. When I do it myself in code I always go back and rename those single letter variables to proper names. It forces me to know what the code actually resembles, not just a formula I learned by heart.

I’m not going to defend single letter names (although shortness does have some virtue compared to some monstrous naming conventions), but...

Most math texts have a fair amount of documentation when formulas are introduced. Perhaps substantially more than the table in this article.

Math papers on the other hand assume that the reader has recursively traversed and read all of the citations and knows most of the notation.

Of course, that’s the whole point of citations and notation. Do you want every single paper to be 500+ pages? I have better things to do trying to figure out where the novel result is in hundreds of pages of the same shit I’ve seen dozens of time already.

What I find interesting is that I actually don't mind the single letters at all. As others have said, a name is a name and I don't find either "substitution" or "ap" any more enlightening than "S". I also find that the currying of the parameters in the JS code is hard to read. As soon as I see the type signatures in the next chart, though, it becomes obvious what it's doing.

Incidentally, the S combinator shows up in the J language as the "monadic hook". If f and g are functions, where f takes two arguments and is written infix (so "x f y" is how you write the application of the arguments x and y to f), (f g) x equals x f (g x). It's useful for certain idioms, like "equals rounddown" (actually written =<.) to mean "is an integer".

The thing with these combinators is that they are so low level, so names for them are almost useless. If you were to program with them directly, you'd learn to use and recognize useful sequences of them. At least that's the theory for APL-like languages like J.

Calm down... The SKI combinators are not meant to be used by people. They are an assembly-like notation developed for language implementors.

Your critique is like someone claiming imperative coders are horrible and don't value naming because of assembly language.

Is there a reason why functional programming algebra insists on using one letter identifiers?

I refer you to my answer to a related question.

https://news.ycombinator.com/item?id=16420361

Mathematicians insist on one-grapheme identifiers, partly due to tradition and aesthetics, and partly because at some point juxtaposition came to represent multiplication, so what xy means would be ambiguous.

It is for purely pragmatic reasons. Try actually writing calculational proofs using long identifiers. You will soon find yourself wanting to be drowned in lava.

Of course, a true programmer delegates even the simplest calculation to a computer, so they have less of a need for notation that is easy to manipulate.

Because it truly doesn't matter what 'x' is. It could be a number, string, an Array, Map, React Component, a very specific VerifiedUserWithBillingAddress object from your domain that you're working in right now.

So then what name do you want to give 'x' in `I = x => x`? Is `something` better, more readable?

If you write these functions ad-hoc in your modules as local helper functions, then by all means, use a more appropriate name:

    [1,2,3,undefined,6].map(anIntegerOrUndefined => anIntegerOrUndefined)

But the functions presented here are not those that you should have to write yourself. They are available in the Haskell base library, in JS you can import ramda or other packages. The important thing is to know how and when to use them.

It's intentionally to get across the idea that you don't, and shouldn't, know anything about these arguments within this scope beyond "this is a function" and "this is an argument". These functions just define how to combine things; if you knew any more about the arguments, it would be breaking the abstraction.

The only better names you could really give are ones like func1, func2, arg1, arg2, which don't add any information, just add noise. Trying to get any more specific than that would leave the reader trying to interpret the meaning of the name, but the whole point is that it's strictly "apply this thing to that in this way, without looking at what they are". Even fix-point, which is unarguably cryptic, really needs a paragraph explanation for the unfamiliar more than it would benefit from better names.

That makes sense for the arguments to the outermost function but not to the function it self. Why call it A instead of apply and the then have a big cheat sheet where you put that A means apply and T means applyTo ?

I think those single-letter names like "S combinator" are a holdover from Math notation, where it was a practical consideration, but in practice in functional programming, those names aren't used (I certainly haven't memorized them); If you look at the Haskell column on the page, you can see that they're actually named for readability (though it might not initially seem like it if you don't do a lot of coding in Haskell):

- K is "const" and C is "flip"; they're generally used to for arguments to a higher order function: "map (const 5) myList", "foldl (flip f) 0 myList"

- Psi is "on", since it's regularly used to construct a new function "h = f `on` g"

- S is a specific type of application, called infix as "f `ap` x", but also has an operator to intentionally make it look more like just line noise: "f < * > x". (Had to add spaces to this operator so HN wouldn't interpret it as italics)

The operators might seem opaque, but the idea is to make it more visually apparent that it's a pattern, not some application-specific business logic. There are lots of concepts of "apply" - there's pure application ($), Applicative application (< * >), Monadic application (=<<), etc. - writing them out would distracting to read. Using operators makes it easier to skim and get the general idea of how the code works without worrying about the underlying structural details, while still being precise about them.

It would definitely be harder to play combinatris with longer identifiers...

http://dirk.rave.org/combinatris/

The S K I combinators were developed as the equivalent of assembly language for functional programs.

In reality, expanding a lambda expression into SKI combinators takes up a lot of space. Since the notation is mainly for language implementors, using the short mnemonics allows you to compress the size of the resultant expression.

It's the same reason why the x86 opcode is named 'mov' not 'move'.

Note that this page should be considered a "cheat sheet", rather than an explanation. For explanations, see the reference section lower in the page.

I like this new ascii table

Reply on news.ycombinator.com