Instantly share code, notes, and snippets.

Embed
What would you like to do?
Common combinators in JavaScript
const I = x => x;
const K = x => y => x;
const A = f => x => f(x);
const T = x => f => f(x);
const W = f => x => f(x)(x);
const C = f => y => x => f(x)(y);
const B = f => g => x => f(g(x));
const S = f => g => x => f(x)(g(x));
const P = f => g => x => y => f(g(x))(g(y));
const Y = f => (g => g(g))(g => f(x => g(g)(x)));
Name # Haskell Ramda Sanctuary Signature
identity I id identity I a → a
constant K const always K a → b → a
apply¹ A ($) call (a → b) → a → b
thrush T (&) applyTo T a → (a → b) → b
duplication W join² unnest² join² (a → a → b) → a → b
flip C flip flip flip (a → b → c) → b → a → c
compose B (.), fmap² map² compose, map² (b → c) → (a → b) → a → c
substitution S ap² ap² ap² (a → b → c) → (a → b) → a → c
psi P on on (b → b → c) → (a → b) → a → a → c
fix-point³ Y fix (a → a) → a

¹) The A-combinator can be implemented as an alias of the I-combinator. Its implementation in Haskell exists because the infix nature gives it some utility. Its implementation in Ramda exists because it is overloaded with additional functionality.

²) Algebras like ap have different implementations for different types. They work like Function combinators only for Function inputs.

³) In JavaScript and other non-lazy languages, it is impossible to implement the Y-combinator. Instead a variant known as the applicative or strict fix-point combinator is implemented. This variant is sometimes rererred to as the Z-combinator.

Note that when I use the word "combinator" in this context, it implies "function combinator in the untyped lambda calculus".

@davidchambers

This comment has been minimized.

davidchambers commented Feb 14, 2016

You could add the Sanctuary combinators to the table. :)

@JAForbes

This comment has been minimized.

JAForbes commented Jul 21, 2016

I have this as a pinned tab and I just stare at it sometimes like the obelisk in 2001.

@tusharmath

This comment has been minimized.

tusharmath commented May 9, 2017

For Y can we use —

  const Y = fn => fn((...t) => Y(fn)(...t))
@poulet42

This comment has been minimized.

poulet42 commented Nov 10, 2017

It seems the T-combinator is implemented as "applyTo" in Ramda – Doc

@Avaq

This comment has been minimized.

Owner

Avaq commented Dec 22, 2017

Thanks @poulet42! I missed the introduction of applyTo to Ramda. I've updated the gist.

@jrsinclair

This comment has been minimized.

jrsinclair commented Jan 9, 2018

I have this as a pinned tab and I just stare at it sometimes like the obelisk in 2001.

@JAForbes Haha. I was just doing the same thing.

@babakness

This comment has been minimized.

babakness commented Feb 11, 2018

Anyone here who could help me with a StackOverflow question to clear my confusion around the definition of S as compared to other libraries implementation of ap, I'd greatly appreciate it.

https://stackoverflow.com/questions/48735774/confusion-in-understanding-substitution-ap-type-signature-and-different-impl

@babakness

This comment has been minimized.

babakness commented Feb 11, 2018

Looking at this

https://github.com/sanctuary-js/sanctuary-type-classes/tree/v7.1.1#ap--applyf--fa-bfa---fb

ap(Identity(Math.sqrt), Identity(64))

Seems more like B, compose

Identity(Math.sqrt(64)) == Identity(8)

@Avaq

This comment has been minimized.

Owner

Avaq commented Feb 11, 2018

@babakness I've answered your question over at SO. I'm not entirely sure what you were looking for though, if you have follow-up questions or would like to discuss something, it's probably easiest to join the Fantasy Land chat.

@glebec

This comment has been minimized.

glebec commented Feb 20, 2018

If it's not too gauche, I'll plug my own talk on lambda calc / combinatorial logic / combinators here, which is in JS rather than Python or Ruby (as some notable previous talks have been):

@rauschma

This comment has been minimized.

rauschma commented Feb 26, 2018

@Avaq Suggestion: in combinators.js, use the same names that you use in the first column of the table. Then it’s easier to read and you don’t need an extra column for IDs.

@fkereki

This comment has been minimized.

fkereki commented Feb 28, 2018

The definition by @tusharmath

const Y = fn => fn((...t) => Y(fn)(...t))

beats the purpose of combinators for recursion; if you allow named functions, the Y combinator isn't needed.

@kirilloid

This comment has been minimized.

kirilloid commented Mar 19, 2018

Great work, I think we need more fundamental stuff like that.
What I don't understand is W. join in Haskell usually collapses a container so its type should be a (a b) → a b rather than (a → a → b) → a → b. Is it some kind of generalization? Or is it what footnote 2 is about?

@dakom

This comment has been minimized.

dakom commented Mar 21, 2018

@glebec - started watching your videos now, fantastic! Fwiw I also thing this page is a fitting place to cross-link it somehow.

@tusharmath

This comment has been minimized.

tusharmath commented Mar 26, 2018

@fkereki The implementation doesn't require the function to be named (AFAIK). Can you show case an example where it's being used that way?

@danwdart

This comment has been minimized.

danwdart commented Nov 4, 2018

You folks might know this...
Is there a name for this combinator?

const foo = f => g => x => y => f(g(x)(y));

I'm often using this one.

It can also be composed by composing compose with compose, confusingly and hilariously (using your definitions, B for composition and W for duplication):

const foo = f => g => x => y => f(g(x)(y));

// foo can be shortened and made more confusing... so all of these are the same thing...
const fooComposed1 = f => g => x => B(f)(g(x));
const fooComposed2 = f => B(B(f));
const fooComposed3 = f => B(B)(B)(f);
// we're finally pointless :p so these are all just the same too:
const fooComposed4 = B(B)(B);
const fooComposed5 = W(B)(B);
const fooComposed6 = W(W)(B);

Thanks.

@glebec

This comment has been minimized.

glebec commented Dec 4, 2018

@danwdart – Smullyan named that the “Blackbird” combinator, sometimes notated B1 (as opposed to the Bluebird B, which is ordinary composition).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment