Combinator Table

Combinators, Birds, Spellings & More

Function Abstraction Symbol AN⁴ Bird CR¹ CH² Elem³ Haskell APL BQN Intro
λa.a I - Identity SKK SKK id ⊣⊢ ⊣⊢ Sch24
λab.a K - Kestrel K K const Sch24
λab.b κ - Kite KI KI
λab.abb W 1y2 Warbler C(BMR) CSK join ˜ Cur29
λabc.acb C 2y2 🐦 Cardinal S(BBS)(KK) B(ΦBS)KK flip ˜ Sch24
λabc.a(bc) B 1y11 Bluebird S(KS)K S(KS)K . ∘⍤⍥ 2T ∘○ 2T Sch24
λabcd.a(bcd) B₁ 2y12 Blackbird BBB DB .: ⍤ 2T ∘ 2T Cur30
λabcde.a(bcde) B2 3y13 Bunting B(BBB)B DB₁ Cur30
λabcd.a(b(cd)) B3 4y14 Becard B(BB)B BDB Cur30
λabc.ac(bc) S 1y21 Starling S S <*> / ap Sch24
λabc.a(bc)c Σ 1y12 Violet Starling - ? =<<
λabcd.ab(cd) D 2y21 Dove BB BB Smu85
λabcd.a(bc)d Δ 2y12 Zebra Dove - ?
λabcd.a(bd)(cd) Φ 1y121 Phoenix - B₁SB liftA2 3T 3T Cur31
λabcd.a(bc)(bd) Ψ 2y21 Psi - B(SΦCB)B on Cur31
λabcde.abc(de) D1 3y31 Dickcissel B(BB) BD
λabcde.a(bc)(de) D2 2y211 Dovekie BB(BB) DD Smu85
λabcde.ab(cde) E 3y22 🦅 Eagle B(BBB) BB₁ Smu85
λabcde.a(bcd)e ε 3y22 Golden Eagle - ?
λabcde.a(bde)(cde) Φ1 2y222 Pheasant - BΦΦ 3T 3T Cur31
λabcdefg.a(bcd)(efg) Ê 4y222 Bald Eagle B(BBB)(B(BBB)) D₂D₂D Smu85

Reference Notes

1 - CR: Chris Rathman (combinator spellings taken from his site)

2 - CH: Conor Hoekstra (combinator spellings generated from C++ program)

3 - Elementary combinators: Listed in Chapter 5 of Combinatory Logic: Volume I

4 - Arity Notation: AyBC = An A-arity yielding binary function (because BC is length two) where the arguments of the function have arity B and C

Papers

Code Author Year Paper
Sch24 Moses Schönfinkel 1924 On the building blocks of mathematical logic
Cur29 Haskell Curry 1929 An Analysis of Logical Substitution
Cur30 Haskell Curry 1931 Grundlagen der Kombinatorischen Logik (The Foundations of Combinatory Logic)
Cur31 Haskell Curry 1931 The universal quantifier in combinatory logic
Cur48 Haskell Curry 1948 A Simplification of the Theory of Combinators
Cur58 H. Curry & R. Feys 1958 Combinatory Logic: Volume I
Tur78 David Turner 1979 Another algorithm for bracket abstraction
Smu85 Raymond Smullyan 1985 To Mock a Mockingbird
Iv89 K. Iverson & E. McDonnell 1989 Phrasal Forms
Loc12 Marshall Lochbaum 2012 Added hook, backhook

“A language that doesn't affect the way you think about programming is not worth knowing.”

— Alan Perlis