# Combinator birds

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:

``keepHalf list = take (length list `div` 2) 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:

``keepHalf = missingBird take ((`div` 2) . length)``

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:

``keepHalf = take <\$> ((`div` 2) . length) <*> id``

Sources:

 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 