Combinators#

Combinators are short closed terms that can be combined with other terms or combinators.

Common#

All of these combinators (and many more) can be found in std/Combinator. The names are taken from Raymond Smullyan's book "To Mock a Mockingbird"1.

y/z: Fixed-point combinators

used to achieve recursion

(y g) = (g (y g))

b/b'/b''' or …∘…/…∘∘…/…∘∘∘…: Blackbird combinators

used to compose two functions with 1/2/3 arguments

((f ∘ g) x) = (f (g x))

(((f ∘∘ g) x) y) = (f ((g x) y))

((((f ∘∘∘ g) x) y) z) = (f (((g x) y) z))

c or \‣: Cardinal combinator

used to flip arguments (e.g. for higher-order application)

((\f x) y) = ((f y) x)

s or …<*>…: Starling combinator

used to apply one argument to two functions (substitution)

((f <*> g) x) = ((f x) (g x))

k or const: Kestrel combinator

used to wrap a term inside an additional abstraction (also for boolean logic)

(k f) = [f]

i (Haskell's id): Kestrel combinator

used as identity function or to indicate an unused argument

(i x) = x

ψ: Psi combinator (Haskell's on)

used to apply two arguments to one function seperately

((((ψ f) g) x) y) = ((f (g x)) (g y))

ω: Mockingbird/omega combinator

used to apply a term to itself

(ω f) = (f f)

Also: Ω = (ω ω)

If you enjoy the use of combinators, you might also enjoy bruijn's sister language Birb.

  1. Smullyan, Raymond M. To Mock a Mockingbird: and other logic puzzles including an amazing adventure in combinatory logic. Oxford University Press, USA, 2000. ↩