sourcelib/Combinators.xtl
1⍝│ Combinators: the birds Raymond Smullyan names in "To Mock a
2⍝│ Mockingbird" that type-check (a standard library, built into xetal).
3⍝│ Import it with an alias of your choice: "c:" u_se< "Combinators".
4⍝│ docs/birds.md lists them all, with two of Curry's that trains name
5⍝│ (the Phoenix and Psi); the self-applying birds (L, M, M2, U) have no
6⍝│ finite type and are in demos/birds-untyped.xtl.
7⍝│
8⍝│ Each bird only rearranges, repeats, drops or groups its curried
9⍝│ arguments; its rule is given in Smullyan's notation, where
10⍝│ B x y z = x (y z) means B applied to x, y and z gives x applied to
11⍝│ (y applied to z).
12⍝│
13⍝│ How the definitions read: a x̲ b is x applied to a and then b (every
14⍝│ function is curried); (e) v applies the function e computes; a
15⍝│ function passed along as a value is quoted, 'y̲. In a call, quoted
16⍝│ function arguments come first, the nearest operand being the bird's
17⍝│ first argument: 'n̲eg 'a̲bs ᶜB̲ -5 is a_bs (n_eg -5).
18
19⍝━━ Identity, constants and duplication
20
21⍝│ The Idiot Bird (identity): I x = x.
22⍝│ >> "c:" u_se< "Combinators"
23⍝│ >> c:I_ 7
24⍝│ 7
25ˡI̲ ← { x → x } ⍝ Idiot Bird (identity)
26
27⍝│ The Kestrel: K x y = x, the first argument kept, the second dropped
28⍝│ (▁, a parameter nothing reads).
29⍝│ >> "c:" u_se< "Combinators"
30⍝│ >> 1 c:K_ 2
31⍝│ 1
32ˡK̲ ← { x ▁ → x } ⍝ Kestrel
33
34⍝│ The Thrush: T x y = y x, the value x given to the function y.
35⍝│ >> "c:" u_se< "Combinators"
36⍝│ >> 3 c:T_ 'n_eg
37⍝│ -3
38ˡT̲ ← { x y̲ → y̲ x } ⍝ Thrush
39
40⍝│ The Warbler: W x y = x y y, the dyadic function x given y twice.
41⍝│ >> "c:" u_se< "Combinators"
42⍝│ >> '* c:W_ 4
43⍝│ 16
44ˡW̲ ← { x̲ y → y x̲ y } ⍝ Warbler
45
46⍝│ The Converse Warbler: W1 x y = y x x, the Warbler with its arguments
47⍝│ the other way round.
48⍝│ >> "c:" u_se< "Combinators"
49⍝│ >> 3 c:W_1 '+
50⍝│ 6
51ˡW̲1 ← { x y̲ → x y̲ x } ⍝ Converse Warbler
52
53⍝━━ Composition
54
55⍝│ The Bluebird: B x y z = x (y z), x composed with y.
56⍝│ >> "c:" u_se< "Combinators"
57⍝│ >> 'n_eg 'a_bs c:B_ -5
58⍝│ 5
59ˡB̲ ← { x̲ y̲ z → x̲ y̲ z } ⍝ Bluebird: compose
60
61⍝│ The Blackbird: B1 x y z w = x (y z w), x after the dyadic y.
62ˡB̲1 ← { x̲ y̲ z w → x̲ z y̲ w } ⍝ Blackbird
63
64⍝│ The Bunting: B2 x y z w v = x (y z w v), x after the triadic y.
65ˡB̲2 ← { x̲ y̲ z w v → x̲ (z y̲ w) v } ⍝ Bunting
66
67⍝│ The Becard: B3 x y z w = x (y (z w)), three functions composed.
68ˡB̲3 ← { x̲ y̲ z̲ w → x̲ y̲ z̲ w } ⍝ Becard
69
70⍝│ The Cardinal: C x y z = x z y, the dyadic x with its arguments
71⍝│ swapped.
72⍝│ >> "c:" u_se< "Combinators"
73⍝│ >> 10 '- c:C_ 3
74⍝│ -7
75ˡC̲ ← { x̲ y z → z x̲ y } ⍝ Cardinal: swap
76
77⍝│ The Dove: D x y z w = x y (z w), z applied to w before x takes it.
78ˡD̲ ← { x̲ y z̲ w → y x̲ z̲ w } ⍝ Dove
79
80⍝│ The Dickcissel: D1 x y z w v = x y z (w v).
81ˡD̲1 ← { x̲ y z w̲ v → (y x̲ z) w̲ v } ⍝ Dickcissel
82
83⍝│ The Dovekie: D2 x y z w v = x (y z) (w v), both arguments of x
84⍝│ computed first.
85ˡD̲2 ← { x̲ y̲ z w̲ v → (y̲ z) x̲ w̲ v } ⍝ Dovekie
86
87⍝│ The Eagle: E x y z w v = x y (z w v).
88ˡE̲ ← { x̲ y z̲ w v → y x̲ w z̲ v } ⍝ Eagle
89
90⍝│ The Bald Eagle: Eh x y1 y2 y3 z1 z2 z3 = x (y1 y2 y3) (z1 z2 z3).
91ˡE̲h ← { x̲ a̲ b c d̲ e f → (b a̲ c) x̲ e d̲ f } ⍝ Bald Eagle
92
93⍝━━ Permutations
94
95⍝│ The Finch: F x y z = z y x, the function last and the values
96⍝│ reversed.
97⍝│ >> "c:" u_se< "Combinators"
98⍝│ >> (1 c:F_ 2)_ '-
99⍝│ 1
100ˡF̲ ← { x y z̲ → y z̲ x } ⍝ Finch
101
102⍝│ The Goldfinch: G x y z w = x w (y z).
103ˡG̲ ← { x̲ y̲ z w → w x̲ y̲ z } ⍝ Goldfinch
104
105⍝│ The Hummingbird: H x y z = x y z y, y used twice.
106ˡH̲ ← { x̲ y z → (y x̲ z) y } ⍝ Hummingbird
107
108⍝│ The Jay: J x y z w = x y (x w z).
109ˡJ̲ ← { x̲ y z w → y x̲ w x̲ z } ⍝ Jay
110
111⍝│ The Owl: O x y = y (x y).
112ˡO̲ ← { x̲ y̲ → y̲ x̲ 'y̲ } ⍝ Owl
113
114⍝│ The Queer Bird: Q x y z = y (x z), composition the other way round
115⍝│ from B.
116⍝│ >> "c:" u_se< "Combinators"
117⍝│ >> 'n_eg 'a_bs c:Q_ -5
118⍝│ -5
119ˡQ̲ ← { x̲ y̲ z → y̲ x̲ z } ⍝ Queer Bird
120
121⍝│ The Quixotic Bird: Q1 x y z = x (z y).
122ˡQ̲1 ← { x̲ y z̲ → x̲ z̲ y } ⍝ Quixotic Bird
123
124⍝│ The Quizzical Bird: Q2 x y z = y (z x).
125ˡQ̲2 ← { x y̲ z̲ → y̲ z̲ x } ⍝ Quizzical Bird
126
127⍝│ The Quirky Bird: Q3 x y z = z (x y).
128ˡQ̲3 ← { x̲ y z̲ → z̲ x̲ y } ⍝ Quirky Bird
129
130⍝│ The Quacky Bird: Q4 x y z = z (y x).
131ˡQ̲4 ← { x y̲ z̲ → z̲ y̲ x } ⍝ Quacky Bird
132
133⍝│ The Robin: R x y z = y z x, the function moved to the front.
134⍝│ >> "c:" u_se< "Combinators"
135⍝│ >> (1 c:R_ '-)_ 2
136⍝│ 1
137ˡR̲ ← { x y̲ z → z y̲ x } ⍝ Robin
138
139⍝│ The Starling: S x y z = x z (y z), z used twice (J's hook).
140⍝│ >> "c:" u_se< "Combinators"
141⍝│ >> 'n_eg '- c:S_ 3
142⍝│ 6
143ˡS̲ ← { x̲ y̲ z → z x̲ y̲ z } ⍝ Starling
144
145⍝│ The Vireo: V x y z = z x y, a pair: x and y held until a function
146⍝│ z is given them.
147⍝│ >> "c:" u_se< "Combinators"
148⍝│ >> (1 c:V_ 2)_ '-
149⍝│ -1
150ˡV̲ ← { x y z̲ → x z̲ y } ⍝ Vireo: a pair
151
152⍝━━ From Curry's aviary
153
154⍝│ The Phoenix (Curry's S', not in Smullyan's list): Phi x y z w =
155⍝│ x (y w) (z w), the fork [y̲ x̲ z̲] w as a bird: two functions of
156⍝│ the same argument, joined by a third.
157⍝│ >> "c:" u_se< "Combinators"
158⍝│ >> 'a_bs 'n_eg '- c:P_hi 3
159⍝│ -6
160ˡP̲hi ← { x̲ y̲ z̲ w → (y̲ w) x̲ z̲ w } ⍝ Phoenix: a fork
161
162⍝│ Psi (Curry's, not in Smullyan's list): Psi x y z w = x (y z) (y w),
163⍝│ one function of both arguments before another joins them.
164⍝│ >> "c:" u_se< "Combinators"
165⍝│ >> 1 2 'a_bs '- c:P_si -3
166⍝│ -2 -1
167ˡP̲si ← { x̲ y̲ z w → (y̲ z) x̲ y̲ w } ⍝ Psi: on
168
169⍝━━ Once removed
170
171⍝│ C once removed: C* x y z w = x y w z.
172ˡC̲s ← { x̲ y z w → (y x̲ w) z }
173
174⍝│ R once removed: R* x y z w = x z w y.
175ˡR̲s ← { x̲ y z w → (z x̲ w) y }
176
177⍝│ F once removed: F* x y z w = x w z y.
178ˡF̲s ← { x̲ y z w → (w x̲ z) y }
179
180⍝│ V once removed: V* x y z w = x w y z.
181ˡV̲s ← { x̲ y z w → (w x̲ y) z }
182
183⍝│ W once removed: W* x y z = x y z z.
184ˡW̲s ← { x̲ y z → (y x̲ z) z }
185
186⍝━━ Twice removed
187
188⍝│ C twice removed: C** x y z w v = x y z v w.
189ˡC̲ss ← { x̲ y z w v → ((y x̲ z) v) w }
190
191⍝│ R twice removed: R** x y z w v = x y w v z.
192ˡR̲ss ← { x̲ y z w v → ((y x̲ w) v) z }
193
194⍝│ F twice removed: F** x y z w v = x y v w z.
195ˡF̲ss ← { x̲ y z w v → ((y x̲ v) w) z }
196
197⍝│ V twice removed: V** x y z w v = x y v z w.
198ˡV̲ss ← { x̲ y z w v → ((y x̲ v) z) w }
199
200⍝│ W twice removed: W** x y z w = x y z w w.
201ˡW̲ss ← { x̲ y z w → ((y x̲ z) w) w }
202
203⍝━━ Recursion
204
205⍝│ The Sage Bird by recursion: Y f is f (Y f), a fixed point of f. It
206⍝│ works because a function's parameter is evaluated only when used; f
207⍝│ takes itself (as ~s_elf) and its argument.
208⍝│ >> "c:" u_se< "Combinators"
209⍝│ >> u:f_act := { ~s_elf n -> n <= 1 ? 1; n * s_elf n - 1 }
210⍝│ >> 'u:f_act c:Y_ 5
211⍝│ 120
212ˡY̲ ← { f̲ → f̲ ˡY̲ 'f̲ }