size

Another polytypic function is size, which counts the number of occurences of values of type $\alpha$ in a structure of type $\mathcal{F}$ $\alpha$.

size for L is just the standard list length function:
sizeL :: L $\alpha$ $\rightarrow$Int
sizeL Nil = 0
sizeL (Cons x xl) = 1 + (sizeL xl)

How about for structures of type G L $\alpha$ (i.e., ``standard'' rose trees)? sizeGL :: G L $\alpha$ $\rightarrow$Int
sizeGL (Branch x xg) = 1 + sum (map sizeGL xg)
While this is clearly the right function, we needed to introduce the functions sum and map.

Let's try B:
sizeB :: B $\alpha$ $\rightarrow$Int
sizeB NilB = 0
sizeB (Cons x xb) = 1 + (sizeB xb)
Well, it type checks, but it doesn't quite work right. The recursive call to sizeB counts the number of Bush $\alpha$'s in xb, not the number of $\alpha$'s. To implement sizeB correctly, we need to generalize a little:
countB :: ($\alpha$ $\rightarrow$Int) $\rightarrow$B $\alpha$ $\rightarrow$Int
countB ca NilB = 0
countB ca (Cons x xb) = (ca x) + (countB (countB ca) xb)
sizeB = countB ($\lambda$ x -> 1)
The function countB generalizes sizeB by taking an argument ca that gives a count for occurences of values of type $\alpha$. For the recursive call to countB, we use countB ca to give a count for each occurence of type B $\alpha$ in xb. Finally, sizeB is simply a specialization of countB by giving each occurence of a value of type $\alpha$ a count of 1.

With this generalization in mind, we can similary implement countG:
countG :: ($\forall \beta$. ($\beta$ $\rightarrow$Int) $\rightarrow$$\mathcal{F}$ $\beta$ $\rightarrow$Int) $\rightarrow$ ($\alpha$ $\rightarrow$Int) $\rightarrow$G $\mathcal{F}$ $\alpha$ $\rightarrow$Int
countG cf ca (Branch x xg) = (ca x) + (cf (countG cf cg) xg)
sizeG :: ($\alpha$ $\rightarrow$Int) $\rightarrow$G $\mathcal{F}$ $\alpha$ $\rightarrow$Int
sizeG cf = countG count$\mathcal{F}$ ($\lambda$ x -> 1)

Finally, we can revisit L:
countL :: ($\alpha$ $\rightarrow$Int) $\rightarrow$L $\alpha$ $\rightarrow$Int
countL ca Nil = 0
countL ca (Cons x xl) = (ca x) + (countL ca xl)
sizeL = countL ($\lambda$ x -> 1)

This exercise has demonstrated a common theme in polytypic programming. Often, when implementing some function, it makes more sense to implement a more general form of the function and obtain the target function as a specialization of the generalized function. To this end, in the next section, we'll implement an even more general function.

Question: how should countD and countC be implemented?