Skip to content

Instantly share code, notes, and snippets.

@Avaq
Last active March 28, 2023 02:13
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 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 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".

@glebec
Copy link

glebec commented Aug 14, 2020

@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
Copy link

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
Copy link

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
Copy link

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
Copy link

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
Copy link

danwdart commented Nov 19, 2020

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
Copy link

drupol commented Nov 19, 2020

Hi,

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

@JamieDixon
Copy link

JamieDixon commented Nov 19, 2020

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

@danwdart
Copy link

Reminds me of the Reader monad with composition.

@JamieDixon
Copy link

@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
Copy link

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
Copy link

@drupol Looks good to me!

@CrossEye
Copy link

@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
Copy link

JamieDixon commented Nov 22, 2020

@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
Copy link

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

@Avaq
Copy link
Author

Avaq commented Dec 23, 2020

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

@danwdart
Copy link

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
Copy link

CrossEye commented Dec 25, 2020

@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
Copy link
Author

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
Copy link

CrossEye commented Dec 29, 2020

@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}) //=> <nonsense>

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
Copy link
Author

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
Copy link

@Avaq:

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)

@stken2050
Copy link

stken2050 commented Sep 28, 2021

a → b → b is also useful:

const right = a => b => b;
const log = a => right(console.log(a))(a);

This behaves like identity function: a => a which does not affect to the original code but console.log(a) in the process.

It's possible to rewrite with a → b → a

const left = a => b => a;
const log = a => left(a)(console.log(a));

but, It's not intuitive in terms of the evaluation order.

@jethrolarson
Copy link

jethrolarson commented Sep 29, 2021

@stken2050 Fortunately its trivial

const CK = C(K)

I don't see why console.log is a good case though. Maybe you meant 'tap':

const tap = (f) => (x) => {
  f(x);
  return x;
};

tap(console.log)(2)

// Or more usefully: 
doThing().then(tap(console.log))

It is impure though

@stken2050
Copy link

@jethrolarson
Thanks.
Sure, log is IO and impure, and actually, I use the right for any IO operations.

@customcommander
Copy link

Hello! Ramda v0.28.0 has shipped with some new functions, including on: https://ramdajs.com/docs/#on — Do you think we could update the table above?

@drupol
Copy link

drupol commented Jan 25, 2022

It looks like that new on is actually the Psi combinator.

@Avaq
Copy link
Author

Avaq commented Jan 26, 2022

Thanks for the heads-up. Ramda on added to the table! 🎉

@CrossEye
Copy link

CrossEye commented Sep 8, 2022

@JAForbes:

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

Six years later, and I'm still doing that!

@Avaq: Thank you for a wonderful resource!

@Avaq
Copy link
Author

Avaq commented Sep 15, 2022

Thank you @CrossEye ❤️
I also still commonly refer to this resource, myself. :)

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