Exercise 2.3
Find types for $K$ and $S$ (see Exercise 1.9).
Let's remind ourselves of $K$ and $S$.
$$\begin{align} K &:= λxy. x \\ \\ S &:= λxyz. xz(yz) \end{align}$$
Let's start with $ K := λxy. x $.
Let's take the type of $x$ as $A$, and the type of $y$ as $B$. Then the type of $K$ is simply
$$K : A \to B \to A$$
Now consider $S := λxyz. xz(yz) $.
Let's parenthesise the term to make its meaning clearer.
$$S := λxyz. (xz)(yz) $$
Let's take the types of the variables as
$$x:A,\; y:B, \; z:C$$
Since $x$ is applied to $z$, and $y$ is applied to $z$, we have
$$\begin{align} A & = C \to D \\ \\ B & = C \to E \end{align}$$
This means the type of $(xz)$ is $D$, and since $(xz)$ is applied to $(yz)$ which has type $E$, the type of $(xz)$ must be $D = E \to F$.
Let's put this together.
$$S : (C \to (E \to F)) \to (C \to E) \to C \to F$$
Let's rename the variables to make it easier to read.
$$S : (B \to (A \to C)) \to (B \to A) \to B \to C$$
Note: I had help to think more systematically about this kind of problem here (link).
