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

source

Identity, constants and duplication

ˡI̲ : Any a => a -> a

function · line 25

The Idiot Bird (identity): I x = x.

      "c:" u̲se< "Combinators"
      ᶜI̲ 7
7
ˡI̲ ← { x → x }                                      ⍝ Idiot Bird (identity)

ˡK̲ : (Any a, Any b) => a -> b -> a

function · line 32

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

function · line 38

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

function · line 44

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

function · line 51

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

function · line 59

The Bluebird: B x y z = x (y z), x composed with y.

      "c:" u̲se< "Combinators"
      'n̲eg 'a̲bs ᶜB̲ -5
5
ˡ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

function · line 62

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

function · line 65

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

function · line 68

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

function · line 75

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

function · line 78

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

function · line 81

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

function · line 85

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

function · line 88

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

function · line 91

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

function · line 100

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

function · line 103

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

function · line 106

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

function · line 109

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

function · line 112

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

function · line 119

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

function · line 122

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

function · line 125

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

function · line 128

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

function · line 131

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

function · line 137

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

function · line 143

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

function · line 150

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

function · line 160

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

function · line 167

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

function · line 172

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

function · line 175

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

function · line 178

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

function · line 181

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

function · line 184

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

function · line 189

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

function · line 192

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

function · line 195

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

function · line 198

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

function · line 201

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

function · line 212

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̲ }