2019-08-26

I've been learning some basics about combinators and birds. My interest came from trying to use point-free style in Haskell extensively.

I browsed through (skipped all the exercises) a book called To Mock a Mockingbird by Raymond Smullyan. It was a joyful read, highly recommended!

I made up a small presentation about point-free style and using basic combinators. The slides are here. Please let me know if I got something wrong.

This page is to tabulate the common combinators, so that I could better get a grasp on their properties and differences. I would appreciate if You let me know if I got something wrong here!

I added one bird myself, the *missing bird*. While trying to implement an imaginary function *keepHalf* which keeps about half of the items in a list:

I needed a combinator which passes the list to an arity-2 function through another function and directly. Since the same need arises for example when filtering a list with a predicate derived from the list itself, it feels like the need is quite common. Otherwise a *starling* would have been a perfect hit, but the arguments of *take* are in the wrong order, where as with *missing bird* no addition bloat is needed:

Why isn't this combinator included in the common combinators? I couldn't even find any references to it in the Internet. Considering only combinators it feels like an important one. In practice I would rather use the *Applicative Functor* of functions since it's so darn simple and elegant:

Sources:

- To Mock a Mockingbird
- http://www.angelfire.com/tx4/cus/combinator/birds.html
- http://dkeenan.com/Lambda/index.htm
- http://hackage.haskell.org/package/data-aviary-0.4.0/docs/Data-Aviary-Birds.html

c o m b i n a t o r |
bird | type | implementation | in Haskell | point-free | intuition | 1. a r g a r i t y |
p e r m u t i n g |
d u p l i c a t i v e |
o r d e r |
r e g u l a r |

I | idiot | a -> a | I x = x I = S K K I = S K S |
id | id | Identity | 1 | x | |||

A I* |
apply / applicator idiot once removed |
(a -> b) -> a -> b | A x y = x y I* = B I |
($) | 1 param to a function of arity 1 | 1 | 2 | x | |||

I** | idiot twice removed | (a -> b -> c) -> a -> b -> c | I** x y z = x y z I** = B I* |
2 params to a function of arity 2 | 2 | 3 | x | ||||

I*** | (a -> b -> c -> d) -> a -> b -> c -> d | I*** x y z w = x y z w I*** = B I** |
3 | 5 | x | ||||||

I**** | (a -> b -> c -> d -> e) -> a -> b -> c -> d -> e | I**** x y z w v = x y z w v I**** = B I*** |
4 | 5 | x | ||||||

K | kestrel | a -> b -> a | K x y = x | const | const | Encoding of true in lambda calculus |
x | ||||

Ki | kite | a -> b -> b | Ki x y = y | const id | Encoding of false in lambda calculus |
||||||

B | bluebird | (b -> c) -> (a -> b) -> a -> c | B x y z = x (y z) B = Q T (Q Q) B = S (K S) K |
(.) | (.) | Composition Pass a value to a function and the result to another function "Add a star" "Add a pass-through argument" |
1 | 3 | x | ||

B1 | blackbird | (c -> d) -> (a -> b -> c) -> a -> b -> d | B1 x y z w = x (y z w) B1 = B B B |
(.) . (.) | Composition of composition and composition Pass two values to a function and the result to another function |
1 | 4 | x | |||

B2 | bunting | (d -> e) -> (a -> b -> c -> d) -> a -> b -> c -> e | B2 x y z w v = x (y z w v) | (.) . (.) . (.) | Composition of composition, composition and composition | 1 | 5 | x | |||

B3 | becard | (c -> d) -> (b -> c) -> (a -> b) -> a -> d | B3 x y z w = x (y (z w)) | (. (.)) . (.) . (.) | Pass a value to a function and the result to another function and the result to another function | 1 | 4 | x | |||

S | starling | (a -> b -> c) -> (a -> b) -> a -> c | S x y z = x z (y z) S = B (B W) (B B C) S = B W* G S = W** G |
Applicative's (<*>) on functions | ap | Pass a value straight and also through a function to another function of arity 2 | 2 | x | 3 | x | |

? | missing bird | (b -> a -> c) -> (a -> b) -> a -> c | ? x y z = x (y z) z | flip (flip . (ap .) . (.)) id | Pass a value through a function and also straight to another function of arity 2 | 2 | 3 | x | |||

Φ | phoenix / starling’ |
(b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d | Φ x y z w = x (y w) (z w) | (ap .) . (.) | Pass a value through two different functions to another function of arity 2 | 2 | x | 4 | x | ||

D B' |
dove bluebird prime |
(a -> c -> d) -> a -> (b -> c) -> b -> d | D x y z w = x y (z w) D = B B |
((.) .) | Pass a value straight and another value through a function to another function of arity 2 | 2 | 4 | x | |||

C' | cardinal prime | (c -> a -> d) -> (b -> c) -> a -> b -> d | C' x y z w = x (y w) z | (flip .) . (.) | Pass a value through a function and another value straight to another function of arity 2 | 2 | x | 4 | x | ||

E | eagle | (a -> d -> e) -> a -> (b -> c -> d) -> b -> c -> e | E x y z w v = x y (z w v) E = B (B B B) E = B B1 |
(((.) . (.)) .) | Pass a value straight and two other values through a function to another function of arity 2 | 2 | 5 | x | |||

D1 | dickcissel | (a -> b -> d -> e) -> a -> b -> (c -> d) -> c -> e | D1 x y z w v = x y z (w v) D1 = B D D1 = B (B B) |
(((.) .) .) | Pass two values straight and a third value through a function to another function of arity 3 | 3 | 5 | x | |||

ψ | psi | (b -> b -> c) -> (a -> b) -> a -> a -> c | ψ x y z w = x (y z) (y w) | on | join . ((flip . ((.) .)) .) . (.) | Pass two values through the same function and pass the results to another function of arity 2 | 2 | 4 | x | ||

D2 | dovekie | (c -> d -> e) -> (a -> c) -> a -> (b -> d) -> b -> e | D2 x y z w v = x (y z) (w v) | (((.) .) .) . (.) | Pass two values through different functions and pass the results to another function of arity 2 | 2 | 5 | x | |||

E^ | bald eagle | (e -> f -> g) -> (a -> b -> e) -> a -> b -> (c -> d -> f) -> c -> d -> g | E^ x y1 y2 y3 z1 z2 z3 = x (y1 y2 y3) (z1 z2 z3) E^ = E E E^ = B(BBB)(B(BBB)) E^ = (B B1)(B B1) |
(((((.) . (.)) .) .) .) . (.) . (.) | Pass two pairs of values through different functions and pass the results to another function of arity 2 Like blackbird, but for two pairs of values |
2 | 7 | x | |||

W | warbler | (a -> a -> b) -> a -> b | W x y = x y y W = C (B M R) W = C W' W = B (T W’) R W = C (H R) W = R (H R) R W = C (S R R) W = C (S (C C) (C C)) W = S T |
flip ap id | Duplicate the value and pass to a function of arity 2 | 2 | 2 | x | |||

W* | warbler once removed | (a -> b -> b -> c) -> a -> b -> c | W* x y z = x y z z W* = B W |
flip flip id . (ap .) | Pass first value straight and duplicate another value to a function of arity 3 | 3 | 3 | x | |||

W** | warbler twice removed | (a -> b -> c -> c -> d) -> a -> b -> c -> d | W** x y z w = x y z w w W** = B (B W) W** = B W* |
flip flip id . ((flip . (ap .)) .) | Pass first two values straight and duplicate third value to a function of arity 4 | 4 | 4 | x | |||

H | hummingbird | (a -> b -> a -> c) -> a -> b -> c | H x y z = x y z y H = B W (B C) H = W* C* H = S R |
flip (ap . (flip .)) id | Pass the two values straight and duplicate first value to a function of arity 3 | 2 | 3 | x | |||

J | jay | (a -> b -> b) -> a -> b -> a -> b | J x y z w = x y (x w z) | ap (flip . ((.) .) . ((.) .)) flip | 2 | x | 4 | ||||

jalt | (a -> c) -> a -> b -> c | jalt x y z = x y | (const .) | Pass first value straight and forget the second value | |||||||

jalt' | (a -> b -> d) -> a -> b -> c -> d | jalt' x y z w = x y z | ((const .) .) | Pass first two values straight and forget the third value | |||||||

𝚪 | gamma | ((a -> b -> c) -> d -> e -> b) -> (a -> b -> c) -> (d -> a) -> d -> e -> c | 𝚪 x y z w v = y (z w) (x y w v) | ap (flip . (ap .) . (((.) .) .) . (.)) | 3 | x | 5 | ||||

M | mockingbird | M x = x x M = O I M = W T M = S T T M = S I I |
Pass the value to itself | 1 | 1 | ||||||

M2 | double mockingbird | M2 x y = x y (x y) M2 = B M |
2 | ||||||||

L | lark | L x y = x (y y) L = Q M L = C B M L = R M B L = B B T M B L = B (T M) B L = B W B |
(. ap id id) | Pass the value to itself and pass the result to another function | 1 | 2 | x | ||||

O | owl | ((a -> b) -> a) -> (a -> b) -> b | O x y = y (x y) O = S I O = Q Q W O = B W Q O = B W (C B) |
ap id | 1 | x | 2 | ||||

Θ | sage | (a -> a) -> a | Θ x = x (Θ x) Θ = S L L |
1 | x | 2 | |||||

U | turing | U x y = y (x x y) U = L O U = L (S I) U = B W (L Q) |
2 | x | 2 | ||||||

G | goldfinch | (b -> c -> d) -> (a -> c) -> a -> b -> d | G x y z w = x w (y z) G = B B C |
(.) . flip | Like D, but arguments in different order | 2 | x | 4 | x | ||

T | thrust | a -> (a -> b) -> b | T x y = y x T = C I T = S (K (S I)) T = Q3 I |
(&) | Like I*, but arguments in different order | x | 2 | ||||

C | cardinal | (a -> b -> c) -> b -> a -> c | C x y z = x z y C = R R R C = B (T (B B T)) (B B T) C = Q Q (Q T) C = G G I I |
flip | Swap argument order Like I**, but arguments in different order |
2 | x | 3 | x | ||

F | finch | b -> a -> (a -> b -> c) -> c | F x y z = z y x F = E T T E T F = B (T T) (B (B B B) T) F = C V |
flip (flip . flip id) | Like I**, but arguments in different order | x | 3 | ||||

R | robin | b -> (a -> b -> c) -> a -> c | R x y z = y z x R = B B T R = CC |
flip flip | Like I**, but arguments in different order | x | 3 | ||||

V | vireo | a -> b -> (a -> b -> c) -> c | V x y z = z x y V = B C T V = C F V = C* T |
flip . flip id | Like I**, but arguments in different order | x | 3 | ||||

R* | robin once removed | (b -> c -> a -> d) -> a -> b -> c -> d | R* x y z w = x z w y R* = C* C* |
flip . (flip .) | Like I***, but arguments in different order | 3 | x | 4 | x | ||

F* | finch once removed | (c -> b -> a -> d) -> a -> b -> c -> d | F* x y z w = x w z y F* = B C* R* |
flip . (flip .) . flip | Like I***, but arguments in different order | 3 | x | 4 | x | ||

C* | cardinal once removed | (a -> c -> b -> d) -> a -> b -> c -> d | C* x y z w = x y w z C* = B C C* = G R |
(flip .) | Like I***, but arguments in different order | 3 | x | 4 | x | ||

V* | vireo once removed | (c -> b -> a -> d) -> a -> b -> c -> d | V* x y z w = x w z y V* = C* F* |
flip . (flip .) . flip | Like I***, but arguments in different order | 3 | x | 4 | x | ||

R** | robin twice removed | (a -> c -> d -> b -> e) -> a -> b -> c -> d -> e | R** x y z w v = x y w v z R** = B R* |
((flip . (flip .)) .) | Like I****, but arguments in different order | 4 | x | 5 | x | ||

F** | finch twice removed | (a -> d -> c -> b -> e) -> a -> b -> c -> d -> e | F** x y z w v = x y v z w F** = B F* |
(((flip .) . flip) .) | Like I****, but arguments in different order | 4 | x | 5 | x | ||

C** | cardinal twice removed | (a -> b -> d -> c -> e) -> a -> b -> c -> d -> e | C** x y z w v = x y z v w C** = B C* |
((flip .) .) | Like I****, but arguments in different order | 4 | x | 5 | x | ||

V** | vireo twice removed | (a -> c -> b -> c -> e) -> a -> b -> c -> c -> e | V** x y z w v = x y v z w V** = B V* |
(((flip .) . flip) .) | Like I****, but arguments in different order | 4 | x | 5 | x | ||

Q | queer | (a -> b) -> (b -> c) -> a -> c | Q x y z = y (x z) Q = C B Q = R R R B Q = R B R Q = B B B T B R Q = B (T B) R Q = B (T B) (B B T) Q = G R Q3 Q = C* Q3 |
(>>>) | flip (.) | Like B, but arguments in different order | 1 | x | 3 | ||

Q1 | quixotic | (b -> c) -> a -> (a -> b) -> c | Q1 x y z = x (z y) Q1 = B C B Q1 = C* B |
(. flip id) . (.) | Like B, but arguments in different order | 1 | x | 3 | x | ||

Q2 | quizzical | a -> (b -> c) -> (a -> b) -> c | Q2 x y z = y (z x) Q2 = R* B Q2 = B C (B C) B Q2 = C (B C B) |
flip (.) . flip id | Like B, but arguments in different order | x | 3 | ||||

Q3 | quirky | (a -> b) -> a -> (b -> c) -> c | Q3 x y z = z (x y) Q3 = B T Q3 = G I |
(flip id .) | Like B, but arguments in different order | 1 | x | 3 | |||

Q4 | quacky | a -> (a -> b) -> (b -> c) -> c | Q4 x y z = z (y x) Q4 = F* B Q4 = C (B T) Q4 = Q1 T Q4 = C Q3 |
(flip id .) . flip id | Like B, but arguments in different order | x | 3 | ||||

W' | converse warbler | a -> (a -> a -> b) -> b | W' x y = y x x W' = B M R W' = M2 R W' = B M (B B T) W' = B (B M B) T W' = H R |
ap (flip . flip id) id | Like W, but arguments in different order | x | 2 |