{{ message }}

Instantly share code, notes, and snippets.

# Avaq/combinators.js

Last active Jul 23, 2021
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 S_ = f => g => x => f (g (x)) (x) const S2 = f => g => h => x => f (g (x)) (h (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` `I`¹ `(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`² `(a → b → c) → (a → b) → a → c`
chain S_³ `(=<<)`² `chain`² `chain`² `(a → b → c) → (b → a) → b → c`
converge S2³ `apply2way`, `liftA2`², `liftM2`² `lift2`² `(b → c → d) → (a → b) → (a → c) → a → d`
psi P `on` `on` `(b → b → c) → (a → b) → a → a → c`
fix-point4 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.

³) I could not find a consistent name for these combinators, but they are common enough in the JavaScript ecosystem to justify their inclusion. I named them myself in order to refer to their implementation.

4) 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. The implementation found in `combinators.js` is the strictly evaluated "Z" combinator, which needs the extra wrapper around `g (g)` on the right hand side.

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

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

### 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 there are two separate inputs… In short though, if `x` and `y` were instead a single input fed into both `g` and `h`, 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

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

### dalefrancis88 commented Jan 27, 2020

 What would be a use case? I'm curious

### Ne4to777 commented Jan 27, 2020

 What would be a use case? I'm curious For Y Combinator for example: const Y = f => U(g => f(x => U(g)(x)))

### Avaq commented Aug 12, 2020

 I added the `chain` and `converge` combinators to the table. I couldn't find a common "one letter" name for these, though, so I named them myself. I included a footnote to clarify this.

### danwdart commented Aug 12, 2020

 There are plenty more from the book and it might be one of those from the combinators book. Most are included in references though.

### glebec commented Aug 14, 2020 • edited

 @kirilloid 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? This reply is years later, so forgive me if you're already way past this point in understanding. But: `join` collapses monadic contexts, not containers. ```-- some type aliases for clearer alignment type List a = [a] type Func i o = i -> o -- general type, then specialized to different monads join :: Monad m => m (m a) -> m a join :: List (List a) -> List a join :: Maybe (Maybe a) -> Maybe a join :: IO (IO a) -> IO a join :: Proxy (Proxy a) -> Proxy a join :: Either x (Either x a) -> Either x a join :: Func i (Func i a) -> Func i a join :: (i -> (i -> a)) -> (i -> a)``` The `join` function fuses together a single nested layer of monadic contexts. What is a monadic context for (A)? Sometimes, it's a "container"-like structure, e.g. list of (A) or either X or (A). Sometimes, however, it's not really a container at all, e.g. function with input type X and output type (A) or an IO program that would produce (A). (The ultimate non-container monad Proxy for (A), defined as `data Proxy a = Proxy`, which has a phantom type param and thus never holds an `a`-type value.) The specific monad cited in this combinators article, corresponding to the `W` combinator, is the "Reader" monad – that is, the monad of functions which take a specified input type (and may have different output types). ```type Reader i o = i -> o -- not allowed to define instances for type aliases, but if you could: instance Monad (Reader i) where -- (implementation elided)``` This type is usually cited in Haskell as `((->) r)` for annoying syntactic reasons. It would be more intuitive as `r -> _` but that syntax isn't allowed in class instance definitions, so we have a sectioned operator `(->)` followed by its first input type (`r`), yielding the type signature of a "function which takes type `r` as its input". ```instance Monad ((->) i) where -- (implementation elided)``` Anyway, since the reader monad is a function with a specific input type, nested reader monads would be something like "a function of input type `r`, and output type (a function with input type `r`, and output type `x`). Or, to use type signatures: ```exampleReader :: R -> X exampleNestedReader :: R -> (R -> X)``` Then, it becomes much clearer (at least, in terms of type signatures) how `join` for the reader monad collapses the `R ->` monads into a single `R ->`: ```-- again, using `Func` as a maybe-less-confusing alias for `->`: join :: Monad m => m (m a) -> m a join :: Func i (Func i a) -> Func i a join :: (i -> (i -> a)) -> (i -> a)``` Remember, the function arrow is right-associative, so `(i -> (i -> a))` is the same as `i -> i -> a`: `join :: (i -> i -> a) -> (i -> a)` And we can again use the right-associativity of `->` to simplify one step further: `join :: (i -> i -> a) -> i -> a` So there we go, `join` in Haskell is the same as the `W` combinator, when we are talking about the Reader monad. (Obviously `join` will not be the same as `W` when `join` is specialized to any other monad, e.g. `List` or `Maybe` or `IO`. That's what the footnote was saying.) The thing we are collapsing, the monadic context, is the input side of a function arrow: `r ->` (written in Haskell typeclass instance sigs as `((->) r)`). You may want to know, what on earth do you use the reader monad for? This is out of scope, but… the short answer is that functions which all take the same input-type can be chained together so they all receive a single value as that input. That value then becomes a dynamic / parameterized shared readable constant – a configuration value which each function can read. So in practice, the reader monad is used in Haskell to make it easy to thread read-only config data through an application. Properly explaining and demonstrating the reader monad in practice is a whole topic unto itself, so I recommend anyone interested consult tutorials/articles/docs/books/videos on the subject. I just wanted to focus on the following major points: Not all monads are containers The `W` combinator is the same as `join` for the reader monad (but not `join` for other monads) The reader monad is "functions of input type `r`" (for some `r` type variable)

### drupol commented Nov 5, 2020

 Hey, I'm following this gist actively :-) I created a PHP project out of it, find it here: https://github.com/loophp/combinator I will add the new combinators tonight!

### JamieDixon commented Nov 19, 2020

 Hey all, I love this list and come back to it regularly. I recently wrote a combinator and I'm trying to find out the name of it. I'll do my best to describe it here and perhaps someone who's knowledgeable in these things will know what it's called. The function signature I've identified is: `(a -> b -> c) -> (a -> c -> d) -> (a -> b -> d)` which is a function that takes 2 binary functions. When a value is applied to the resulting function, that value is applied to both of the binary functions. When the next value is applied it is then applied to the second function in the composition, the result of which is applied to the first function in the composition. It's a little bit like `substitution` but for 2 binary functions instead of 1 unary and 1 binary. My implementation of this (using Crocks) looks like: `const fooComb = converge(binary(compose));` Thanks again for maintaining this excellent list and I hope my explanation above is expressed clearly enough.

### davidchambers commented Nov 19, 2020

 As far as I'm aware, @JamieDixon, that combinator does not have a name. When a value is applied to the resulting function, that value is applied to both of the binary functions. Functions are applied to arguments, not the other way around. `f (x)` is `f` applied to `x`. I know what you meant, of course. :)

### JamieDixon commented Nov 19, 2020

 Thanks @davidchambers You are of course completely right, that functions are applied to arguments. I'm not sure why I wrote it that way around! I'm excited to find out that I've produced a combinator without a name. Perhaps I shall name it 🙂

### danwdart commented Nov 19, 2020 • edited

 As far as your `(a -> b -> c) -> (a -> c -> d) -> (a -> b -> d)`, could you provide an instance? It sounds a little like some things I've seen before and might be able to be abstracted. For instance, it seems like a flipped compose with an extra argument.

### drupol commented Nov 19, 2020

 Hi, I'm also curious to see an instance of that.

### JamieDixon commented Nov 19, 2020 • edited

 @danwdart @drupol Let me know if I've misunderstood what you're asking for, but here's how I make use of this function, including some example functions for my app: ``````const filterBodyProps = id => body => ... const parseObject = id => obj => ... // The combinator that is thus-far unnamed // fooComb is now: (a -> b -> c) -> (a -> c -> d) -> (a -> b -> d) const fooComb = converge(binary(compose)); const filterAndParseFields = fooComb(parseObject, filterBodyProps); const result = filterAndParseFields("abc-123")({ name: "bob", price: "500"}) `````` I've been wondering whether the first two functions should be swapped around to bring this more inline with the standard thinking around composition.

### JamieDixon commented Nov 19, 2020

 @danwdart Yes! That's a great way to express it. In this case the `id` is the shared context and the rest is standard function composition.

### drupol commented Nov 19, 2020

 For some reason it's easier for me to use the JS notation: `const FooComb = f => g => x => y => g(x)(f(x)(y))` Is it good @JamieDixon ?

### JamieDixon commented Nov 19, 2020

 @drupol Looks good to me!

### CrossEye commented Nov 20, 2020

 @JamieDixon: I came here wondering if the combinator I was about to write had a well-known name. I guess not. But now I think `FooComb` may be stuck in my head!

### JamieDixon commented Nov 22, 2020 • edited

 @CrossEye Should I leave this earth having achieved nothing more than contributing the name `fooComb` to the collective parlance of combinatorial logic, I shall consider my time here well spent.

### JohanWiltink commented Dec 22, 2020

 `converge` is not well-known in Haskell as `apply2way`. It is very well-known as `liftA2` or `liftM2`.

### Avaq commented Dec 23, 2020

 Right, thanks for the heads-up @JohanWiltink. Noted.

### danwdart commented Dec 23, 2020

 S_ is also known in JS as "flatMap" I'm making a paper / repo combination detailing some of the things you can do with these, and also including the appropriate Smullyan bird (if they exist) in them.

### CrossEye commented Dec 25, 2020 • edited

 @JohanWiltink: Yes I always suggest people use Ramda's `lift` in preference to `converge` whenever they can. `converge` has some additional capabilities for JS's variadic functions, but unless they're used, `lift` is nicer.

### Avaq commented Dec 28, 2020

 @CrossEye I believe I still can't quite list `R.lift` as an implementation of `(b → c → d) → (a → b) → (a → c) → a → d`, because `R.lift` takes its first function argument in strictly uncurried form. As in, I think `R.lift` could be an implementation of `((b, c) → d) → (a → b) → (a → c) → a → d` instead.

### CrossEye commented Dec 29, 2020 • edited

 @Avaq: sorry, I wasn't suggesting that, only responding to something @JohanWiltink said. And yes, it's not an implementation of that pattern, although the first argument can in fact be a curried function. The next functions, though, cannot be supplied separately. So you can do `lift ((a) => (b) => a + b) (x => x.a, x => x.b) ({a: 2, b: 3}) //=> 5` But not `lift ((a) => (b) => a + b) (x => x.a) (x => x.b) ({a: 2, b: 3}) //=> ` So it's more like `(b → c → d) → ((a → b), (a → c)) → a → d` (although as usual with Ramda functions, the first argument can be uncurried or curried.)

### Avaq commented Dec 29, 2020

 I wasn't suggesting that [`R.lift` is a valid implementation of the converge combinator], only responding to something I know, but when I saw your comment I flew in to add `R.lift` to the table, but then started to question whether I can. I commented just to verify. Sorry, it was a little unclear. :) although as usual with Ramda functions, the first argument can be uncurried or curried Oh, interesting. I didn't know Ramda functions are also overloaded in that respect. Also, I thought `R.lift` determines the arity for the lifted function based on the arity of the original, but I guess it uses the length of arguments supplied to the lifted result instead.

### CrossEye commented Dec 29, 2020

 I commented just to verify. You're correct. `lift` is related, but not an exact match, as is Ramda's `converge`. Also, I thought `R.lift` determines the arity for the lifted function based on the arity of the original, but I guess it uses the length of arguments supplied to the lifted result instead. Your initial thought was correct. However if those two numbers don't match, it probably won't work. And of course, this use of `lift` is still a fairly obscure one. I would expect it more for cases like `lift ((a, b) => a + b) (Maybe (25), Maybe (17)) //=> Maybe (42)`