Architecturally Elegant - lahteenmaki.net

Combinator birds

Jyri-Matti Lähteenmäki

2019-08-26

Tags: combinators fp haskell math

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