librarylib/Combinators.xtl
Combinators: the birds Raymond Smullyan names in "To Mock a Mockingbird" that type-check (a standard library, built into xetal). Import it with an alias of your choice: "c:" u_se< "Combinators". docs/birds.md lists them all, with two of Curry's that trains name (the Phoenix and Psi); the self-applying birds (L, M, M2, U) have no finite type and are in demos/birds-untyped.xtl.
Each bird only rearranges, repeats, drops or groups its curried arguments; its rule is given in Smullyan's notation, where B x y z = x (y z) means B applied to x, y and z gives x applied to (y applied to z).
How the definitions read: a x̲ b is x applied to a and then b (every
function is curried); (e) v applies the function e computes; a
function passed along as a value is quoted, 'y̲. In a call, quoted
function arguments come first, the nearest operand being the bird's
first argument: 'n̲eg 'a̲bs ᶜB̲ -5 is a_bs (n_eg -5).
Identity, constants and duplication
ˡI̲ : Any a => a -> a
ˡI̲ ← { x → x } ⍝ Idiot Bird (identity)
ˡK̲ : (Any a, Any b) => a -> b -> a
The Kestrel: K x y = x, the first argument kept, the second dropped
(▁, a parameter nothing reads).
"c:" u̲se< "Combinators"
1 ᶜK̲ 2 1
ˡK̲ ← { x ▁ → x } ⍝ Kestrel
ˡT̲ : (Any a, Any b) => a -> (a -> b) -> b
The Thrush: T x y = y x, the value x given to the function y.
"c:" u̲se< "Combinators"
3 ᶜT̲ 'n̲eg -3
ˡT̲ ← { x y̲ → y̲ x } ⍝ Thrush
ˡW̲ : (Any a, Any b) => (a -> a -> b) -> a -> b
The Warbler: W x y = x y y, the dyadic function x given y twice.
"c:" u̲se< "Combinators"
'× ᶜW̲ 4 16
ˡW̲ ← { x̲ y → y x̲ y } ⍝ Warbler
ˡW̲1 : (Any a, Any b) => a -> (a -> a -> b) -> b
The Converse Warbler: W1 x y = y x x, the Warbler with its arguments the other way round.
"c:" u̲se< "Combinators"
3 ᶜW̲1 '+ 6
ˡW̲1 ← { x y̲ → x y̲ x } ⍝ Converse Warbler
Composition
ˡB̲ : (Any a, Any b, Any c) => (a -> b) -> (c -> a) -> c -> b
ˡB̲ ← { x̲ y̲ z → x̲ y̲ z } ⍝ Bluebird: compose
ˡB̲1 : (Any a, Any b, Any c, Any d) => (a -> b) -> (c -> d -> a) -> c -> d -> b
The Blackbird: B1 x y z w = x (y z w), x after the dyadic y.
ˡB̲1 ← { x̲ y̲ z w → x̲ z y̲ w } ⍝ Blackbird
ˡB̲2 : (Any a, Any b, Any c, Any d, Any e) => (a -> b) -> (c -> d -> e -> a) -> c -> d -> e -> b
The Bunting: B2 x y z w v = x (y z w v), x after the triadic y.
ˡB̲2 ← { x̲ y̲ z w v → x̲ (z y̲ w) v } ⍝ Bunting
ˡB̲3 : (Any a, Any b, Any c, Any d) => (a -> b) -> (c -> a) -> (d -> c) -> d -> b
The Becard: B3 x y z w = x (y (z w)), three functions composed.
ˡB̲3 ← { x̲ y̲ z̲ w → x̲ y̲ z̲ w } ⍝ Becard
ˡC̲ : (Any a, Any b, Any c) => (a -> b -> c) -> b -> a -> c
The Cardinal: C x y z = x z y, the dyadic x with its arguments swapped.
"c:" u̲se< "Combinators"
10 '− ᶜC̲ 3 -7
ˡC̲ ← { x̲ y z → z x̲ y } ⍝ Cardinal: swap
ˡD̲ : (Any a, Any b, Any c, Any d) => (a -> b -> c) -> a -> (d -> b) -> d -> c
The Dove: D x y z w = x y (z w), z applied to w before x takes it.
ˡD̲ ← { x̲ y z̲ w → y x̲ z̲ w } ⍝ Dove
ˡD̲1 : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c -> d) -> a -> b -> (e -> c) -> e -> d
The Dickcissel: D1 x y z w v = x y z (w v).
ˡD̲1 ← { x̲ y z w̲ v → (y x̲ z) w̲ v } ⍝ Dickcissel
ˡD̲2 : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c) -> (d -> a) -> d -> (e -> b) -> e -> c
The Dovekie: D2 x y z w v = x (y z) (w v), both arguments of x computed first.
ˡD̲2 ← { x̲ y̲ z w̲ v → (y̲ z) x̲ w̲ v } ⍝ Dovekie
ˡE̲ : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c) -> a -> (d -> e -> b) -> d -> e -> c
The Eagle: E x y z w v = x y (z w v).
ˡE̲ ← { x̲ y z̲ w v → y x̲ w z̲ v } ⍝ Eagle
ˡE̲h : (Any a, Any b, Any c, Any d, Any e, Any f, Any g) => (a -> b -> c) -> (d -> e -> a) -> d -> e -> (f -> g -> b) -> f -> g -> c
The Bald Eagle: Eh x y1 y2 y3 z1 z2 z3 = x (y1 y2 y3) (z1 z2 z3).
ˡE̲h ← { x̲ a̲ b c d̲ e f → (b a̲ c) x̲ e d̲ f } ⍝ Bald Eagle
Permutations
ˡF̲ : (Any a, Any b, Any c) => a -> b -> (b -> a -> c) -> c
The Finch: F x y z = z y x, the function last and the values reversed.
"c:" u̲se< "Combinators"
(1 ᶜF̲ 2) '− 1
ˡF̲ ← { x y z̲ → y z̲ x } ⍝ Finch
ˡG̲ : (Any a, Any b, Any c, Any d) => (a -> b -> c) -> (d -> b) -> d -> a -> c
The Goldfinch: G x y z w = x w (y z).
ˡG̲ ← { x̲ y̲ z w → w x̲ y̲ z } ⍝ Goldfinch
ˡH̲ : (Any a, Any b, Any c) => (a -> b -> a -> c) -> a -> b -> c
The Hummingbird: H x y z = x y z y, y used twice.
ˡH̲ ← { x̲ y z → (y x̲ z) y } ⍝ Hummingbird
ˡJ̲ : (Any a, Any b) => (a -> b -> b) -> a -> b -> a -> b
The Jay: J x y z w = x y (x w z).
ˡJ̲ ← { x̲ y z w → y x̲ w x̲ z } ⍝ Jay
ˡO̲ : (Any a, Any b) => ((a -> b) -> a) -> (a -> b) -> b
The Owl: O x y = y (x y).
ˡO̲ ← { x̲ y̲ → y̲ x̲ 'y̲ } ⍝ Owl
ˡQ̲ : (Any a, Any b, Any c) => (a -> b) -> (b -> c) -> a -> c
The Queer Bird: Q x y z = y (x z), composition the other way round from B.
"c:" u̲se< "Combinators"
'n̲eg 'a̲bs ᶜQ̲ -5 -5
ˡQ̲ ← { x̲ y̲ z → y̲ x̲ z } ⍝ Queer Bird
ˡQ̲1 : (Any a, Any b, Any c) => (a -> b) -> c -> (c -> a) -> b
The Quixotic Bird: Q1 x y z = x (z y).
ˡQ̲1 ← { x̲ y z̲ → x̲ z̲ y } ⍝ Quixotic Bird
ˡQ̲2 : (Any a, Any b, Any c) => a -> (b -> c) -> (a -> b) -> c
The Quizzical Bird: Q2 x y z = y (z x).
ˡQ̲2 ← { x y̲ z̲ → y̲ z̲ x } ⍝ Quizzical Bird
ˡQ̲3 : (Any a, Any b, Any c) => (a -> b) -> a -> (b -> c) -> c
The Quirky Bird: Q3 x y z = z (x y).
ˡQ̲3 ← { x̲ y z̲ → z̲ x̲ y } ⍝ Quirky Bird
ˡQ̲4 : (Any a, Any b, Any c) => a -> (a -> b) -> (b -> c) -> c
The Quacky Bird: Q4 x y z = z (y x).
ˡQ̲4 ← { x y̲ z̲ → z̲ y̲ x } ⍝ Quacky Bird
ˡR̲ : (Any a, Any b, Any c) => a -> (b -> a -> c) -> b -> c
The Robin: R x y z = y z x, the function moved to the front.
"c:" u̲se< "Combinators"
(1 ᶜR̲ '−) 2 1
ˡR̲ ← { x y̲ z → z y̲ x } ⍝ Robin
ˡS̲ : (Any a, Any b, Any c) => (a -> b -> c) -> (a -> b) -> a -> c
The Starling: S x y z = x z (y z), z used twice (J's hook).
"c:" u̲se< "Combinators"
'n̲eg '− ᶜS̲ 3 6
ˡS̲ ← { x̲ y̲ z → z x̲ y̲ z } ⍝ Starling
ˡV̲ : (Any a, Any b, Any c) => a -> b -> (a -> b -> c) -> c
The Vireo: V x y z = z x y, a pair: x and y held until a function z is given them.
"c:" u̲se< "Combinators"
(1 ᶜV̲ 2) '− -1
ˡV̲ ← { x y z̲ → x z̲ y } ⍝ Vireo: a pair
From Curry's aviary
ˡP̲hi : (Any a, Any b, Any c, Any d) => (a -> b -> c) -> (d -> a) -> (d -> b) -> d -> c
The Phoenix (Curry's S', not in Smullyan's list): Phi x y z w =
x (y w) (z w), the fork [y̲ x̲ z̲] w as a bird: two functions of
the same argument, joined by a third.
"c:" u̲se< "Combinators"
'a̲bs 'n̲eg '− ᶜP̲hi 3 -6
ˡP̲hi ← { x̲ y̲ z̲ w → (y̲ w) x̲ z̲ w } ⍝ Phoenix: a fork
ˡP̲si : (Any a, Any b, Any c) => (a -> a -> b) -> (c -> a) -> c -> c -> b
Psi (Curry's, not in Smullyan's list): Psi x y z w = x (y z) (y w), one function of both arguments before another joins them.
"c:" u̲se< "Combinators"
1 2 'a̲bs '− ᶜP̲si -3 -2 -1
ˡP̲si ← { x̲ y̲ z w → (y̲ z) x̲ y̲ w } ⍝ Psi: on
Once removed
ˡC̲s : (Any a, Any b, Any c, Any d) => (a -> b -> c -> d) -> a -> c -> b -> d
C once removed: C* x y z w = x y w z.
ˡC̲s ← { x̲ y z w → (y x̲ w) z }
ˡR̲s : (Any a, Any b, Any c, Any d) => (a -> b -> c -> d) -> c -> a -> b -> d
R once removed: R* x y z w = x z w y.
ˡR̲s ← { x̲ y z w → (z x̲ w) y }
ˡF̲s : (Any a, Any b, Any c, Any d) => (a -> b -> c -> d) -> c -> b -> a -> d
F once removed: F* x y z w = x w z y.
ˡF̲s ← { x̲ y z w → (w x̲ z) y }
ˡV̲s : (Any a, Any b, Any c, Any d) => (a -> b -> c -> d) -> b -> c -> a -> d
V once removed: V* x y z w = x w y z.
ˡV̲s ← { x̲ y z w → (w x̲ y) z }
ˡW̲s : (Any a, Any b, Any c) => (a -> b -> b -> c) -> a -> b -> c
W once removed: W* x y z = x y z z.
ˡW̲s ← { x̲ y z → (y x̲ z) z }
Twice removed
ˡC̲ss : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c -> d -> e) -> a -> b -> d -> c -> e
C twice removed: C** x y z w v = x y z v w.
ˡC̲ss ← { x̲ y z w v → ((y x̲ z) v) w }
ˡR̲ss : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c -> d -> e) -> a -> d -> b -> c -> e
R twice removed: R** x y z w v = x y w v z.
ˡR̲ss ← { x̲ y z w v → ((y x̲ w) v) z }
ˡF̲ss : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c -> d -> e) -> a -> d -> c -> b -> e
F twice removed: F** x y z w v = x y v w z.
ˡF̲ss ← { x̲ y z w v → ((y x̲ v) w) z }
ˡV̲ss : (Any a, Any b, Any c, Any d, Any e) => (a -> b -> c -> d -> e) -> a -> c -> d -> b -> e
V twice removed: V** x y z w v = x y v z w.
ˡV̲ss ← { x̲ y z w v → ((y x̲ v) z) w }
ˡW̲ss : (Any a, Any b, Any c, Any d) => (a -> b -> c -> c -> d) -> a -> b -> c -> d
W twice removed: W** x y z w = x y z w w.
ˡW̲ss ← { x̲ y z w → ((y x̲ z) w) w }
Recursion
ˡY̲ : Any a => (a -> a) -> a
The Sage Bird by recursion: Y f is f (Y f), a fixed point of f. It works because a function's parameter is evaluated only when used; f takes itself (as ~s_elf) and its argument.
"c:" u̲se< "Combinators"
ᵘf̲act ← { ~s̲elf n → n ≤ 1 ? 1◆ n × s̲elf n − 1 }
'ᵘf̲act ᶜY̲ 5 120
ˡY̲ ← { f̲ → f̲ ˡY̲ 'f̲ }