g33k57

6/14/2019 - 8:15 PM

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

- To Mock a Mocking Bird (book of combinatory puzzles and examples)
- Combinator Birds (summary of all combinators named by the book)
- CombinatorsJS (implementation of all the same combinators in JavaScripts)
- Fantasy Combinators (implementation of common combinators in JavaScript)
- Collected Lambdas (collection of noteworthy combinators)
- Programming With Nothing (talk)
- Church Encoding (wikipedia)
- Fixed-point combinator (wikipedia)
- Lambda calculus (wikipedia)
- SKI combinator calculus (wikipedia)
- BCKW combinator calculus (wikipedia)