Skip to content

Instantly share code, notes, and snippets.

@Avaq
Last active June 22, 2024 19:27
Show Gist options
  • Save Avaq/1f0636ec5c8d6aed2e45 to your computer and use it in GitHub Desktop.
Save Avaq/1f0636ec5c8d6aed2e45 to your computer and use it in GitHub Desktop.
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-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.

³) 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.

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

@dotnetCarpenter
Copy link

dotnetCarpenter commented Dec 30, 2023

@glebec don't be dissatisfied - you have given me plenty to work through and its great fun!
So far I have only worked with the Bool adt. I'm posting it here, so you can comment if I have misunderstood. I plan to go through the other types later.

//                case arguments
//            /-------------------\
const True  = trueCase => falseCase => trueCase
const False = trueCase => falseCase => falseCase
//            \________________________________/
//                     boolean encoding
// Scott encoding:
// Bool  = True | False
// True  = \x _ -> x
// False = \_ y -> y
var darkMode = False
var backgroundColor = darkMode ("black") ("white") // using the `darkMode` bool
console.debug (darkMode,        // <- Function: False
               backgroundColor) // <- white

var darkMode = True
var backgroundColor = darkMode ("black") ("white") // using the `darkMode` bool
console.debug (darkMode,        // <- Function: True
               backgroundColor) // <- black

// wrapped values (constructor args)
//           /----\
const Pair = x => y => access => access(x) (y)
//                     \_____________________/
//                          pair encoding
//           \-------------------------------/
//                     constructor
// Scott encoding:
// Pair x y = Fst | Snd
// Fst      = \x _ -> x
// Snd      = \_ y -> y
const numPair = Pair (5)    (9)
const strPair = Pair ("hi") ("bye")
var   fst     = x => _ => x
var   snd     = _ => y => y
console.debug (numPair (snd), // <- 9
               strPair (snd)) // <- bye

// Pair can also be derived from Bool
// Scott encoding:
// Pair x y    = Bool = True | False
// True  = Fst = \x _ -> x
// False = Snd = \_ y -> y
var fst        = True
var snd        = False
console.debug (numPair (snd), // <- 9
               strPair (snd)) // <- bye

@dotnetCarpenter
Copy link

@glebec I can see that my Scott encoding of Pair is wrong. But what should it be?

Pair x y = x y (\x _ -> x) | x y (\_ y -> y)?

@JohanWiltink
Copy link

JohanWiltink commented Dec 30, 2023

Pair x y = \ fn . fn x y

functionally equivalent to Pair x y fn = fn x y, but trying to express that a pair is a ( binary ) function that accepts a ( binary ) function and applies that function to the values contained in the closure / pair.

The Scott encoding is Pair x y = Pair x y, which seems unhelpful. But note that there is only one, binary, constructor, which is entirely different from Boolean, where there are two nullary constructors.

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