Instantly share code, notes, and snippets.

# Avaq/combinators.js Last active Jan 27, 2020

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 commented Feb 14, 2016

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

### JAForbes commented Jul 21, 2016

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

### poulet42 commented Nov 10, 2017

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

### Avaq commented Dec 22, 2017

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

### 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 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 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)`
Owner Author

### 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 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 commented Feb 26, 2018 • edited

 @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 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 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?

### tusharmath commented Mar 26, 2018 • edited

 @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 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 commented Dec 4, 2018 • edited

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

### danwdart commented Dec 22, 2018 • edited

 Ah - so presumably `B1` is `B(B(x))` so `B2` might be `B(B(B(x)))`? Ooh, nice. Thanks. There is a list like the above that I can check for the names of combinators I rediscover! [edit: I didn't look at the 2nd and 4th links] I don't know... I've got a `f => g => x => y => f(g(x)(g(y)))` which I guess is some kind of decorated `S`/`ap`, and I use applied apply a lot for just calling...

### glebec commented Jan 25, 2019

 so presumably `B1` is `B(B(x))` so `B2` might be `B(B(B(x)))`? Yep. Smullyan's `B2` is `a => b => c => d => e => a(b(c)(d)(e))`. `f => g => x => y => f(g(x)(g(y)))` That's pretty much analogous to Haskell's `Data.Function.on` (minus the exception of the additional typing constraints Haskell enforces over JS). I don't think it has a common combinator name.

### cuihtlauac commented May 7, 2019

 Here is the Z combinator: `const Z = f => (g => f(x => g(g)(x)))(g => f(x => g(g)(x)));`

### dalefrancis88 commented Jul 15, 2019

 hey @danwdart and @glebec do you guys, or anyone else, know if this combinator has a common name? it's a bit like the `psi` and `converge` combinators `const combin = f => g => h => x => y => f(g(x))(h(y))`

### glebec commented Jul 15, 2019 • edited

 @dalefrancis88 the closest I can see in http://www.angelfire.com/tx4/cus/combinator/birds.html is D2 ("Dovekies"), defined there as `labcde.a(bc)(de)`. Your function corresponds to `labcde.a(bd)(ce)` which is identical except for parameter order. So some mix of `flip` and similar combinators would transform D2 to your combinator. The next thing I tried was doing a hoogle search which yielded a Haskell function, `compose2`, from the `Util` library. This isn't a very common function in Haskell but its use case seems clear enough, run different functions on two inputs and then run a function to combine their results. REDACTED I had another section here about the Haskell `Applicative` function `liftA2` but I think it doesn't actually apply here because the two input values may have different types… In short though, if `x` and `y` were always the same type, then we could express this function in Haskell as simply `combin = liftA2`. Or using some well-known combinators, it would be equivalent to `combin f g h = S (B f g) h`.

### dalefrancis88 commented Jul 15, 2019

 Thanks mate that's a nice response, appreciate the answer

### dalefrancis88 commented Jul 19, 2019

 @Avaq What about adding in `converge` `(a → b → c → d) → (a → b) → (a → c) → a → d`

### jethrolarson commented Aug 27, 2019

 converge should be `(b → c → d) → (a → b) → (a → c) → a → d` I think
Owner Author

### Avaq commented Aug 28, 2019

 @jethrolarson I think that's `lift2` in Sanctuary. Might be nice adding that to the table.

### jethrolarson commented Aug 28, 2019

 Yeah, its `converge` in crocks and `apply2way` in Haskell … On Wed, Aug 28, 2019, 8:35 AM Aldwin Vlasblom ***@***.***> wrote: @jethrolarson I think that's lift2 in Sanctuary. Might be nice adding that to the table. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub , or mute the thread .

### michelemendel commented Nov 3, 2019

 Why isn't Crocks (https://crocks.dev/docs/functions/combinators.html) in the list?