macrocephalopod

Converting it to math gives T(x) = 1 + xT(x)^2 which you can solve with the quadratic formula (what) to give T(x) = (1 - sqrt(1 - 4x))/(2x)

The functions you derive from the algebraic data type are called "generating functions" and they are useful for all kinds of counting problems with unlabeled data (ordinary gf) or labeled data (exponential gf) or probability problems (probability generating function)

The mind-blowingly cool thing is that you can differentiate the generating function to get a new function, and if you turn that back into an ADT, it is the zipper type associated with the original ADT (that is, the full data structure plus a 'focus' that you can move around)

I first saw this in a Conor McBride paper from about 2000 but I'm not sure if that's the first time it was noticed, as once you have the ADT <--> generating function correspondence, differentiating it seems like quite a natural thing to do http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.176.2720&rep=rep1&type=pdf …