<p>Binary trees are defined by the equation <code>T=1+XT^2</code> in the semiring of types. By construction, <code>T=(1-sqrt(1-4X))/(2X)</code> is defined by the same equation in the semiring of complex numbers. So given that we're solving the same equation in the same class of algebraic structure it actually shouldn't be surprising that we see some similarities.</p>

<p>The catch is that when we reason about polynomials in the semiring of complex numbers we typically use the fact that the complex numbers form a ring or even a field so we find ourselves using operations such as subtraction that don't apply to semirings. But we can often eliminate subtractions from our arguments if we have a rule that allows us to cancel from both sides of an equation. This is the kind of thing proved by <a href="http://arxiv.org/abs/math/0212377v1">Fiore and Leinster</a> showing that many arguments about rings can be transferred to semirings.</p>

<p>This means that lots of your mathematical knowledge about rings can be reliably transferred to types. As a result, some arguments involving complex numbers or power series (in the ring of formal power series) can carry over to types in a completely rigorous way.</p>

<p>However there's more to the story than this. It's one thing to prove two types are equal (say) by showing two power series are equal. But you can also deduce information about types by inspecting the terms in the power series. I'm not sure of what the formal statement here should be. (I recommend Brent Yorgey's <a href="http://www.cis.upenn.edu/~byorgey/pub/species-pearl.pdf">paper</a> on <a href="http://en.wikipedia.org/wiki/Combinatorial_species">combinatorial species</a> for some work that's closely related but species are <em>not</em> the same as types.)</p>

<p>What I find utterly mind blowing is that what you've discovered can be extended to calculus. Theorems about calculus can be transferred over to the semiring of types. In fact, even arguments about finite differences can be transferred over and you find that classical theorems from numerical analysis have interpretations in type theory.</p>

<p>Have fun!</p>
Abusing the algebra of algebraic data types - why does this work?
<p>The 'algebraic' expression for algebraic data types looks very suggestive to someone with a background in mathematics. Let me try to explain what I mean.</p>

<p>Having defined the basic types</p>

<ul>
<li>Product <code>•</code></li>
<li>Union <code>+</code></li>
<li>Singleton <code>X</code></li>
<li>Unit <code>1</code></li>
</ul>

<p>and using the shorthand <code>X²</code> for <code>X•X</code> and <code>2X</code> for <code>X+X</code> et cetera, we can then define algebraic expressions for e.g. linked lists</p>

<p><code>data List a = Nil | Cons a (List a)</code> ↔ <code>L = 1 + X • L</code></p>

<p>and binary trees:</p>

<p><code>data Tree a = Nil | Branch a (Tree a) (Tree a)</code> ↔ <code>T = 1 + X • T²</code></p>

<p>Now, my first instinct as a mathematician is to go nuts with these expressions, and try to solve for <code>L</code> and <code>T</code>. I could do this through repeated substitution, but it seems much easier to abuse the notation horrifically and pretend I can rearrange it at will. For example, for a linked list:</p>

<p><code>L = 1 + X • L</code></p>

<p><code>(1 - X) • L = 1</code></p>

<p><code>L = 1 / (1 - X) = 1 + X + X² + X³ + ...</code></p>

<p>where I've used the power series expansion of <code>1 / (1 - X)</code> in a totally unjustified way to derive an interesting result, namely that an <code>L</code> type is either <code>Nil</code>, or it contains 1 element, or it contains 2 elements, or 3, etc.</p>

<p>It gets more interesting if we do it for binary trees:</p>

<p><code>T = 1 + X • T²</code></p>

<p><code>X • T² - T + 1 = 0</code></p>

<p><code>T = (1 - √(1 - 4 • X)) / (2 • X)</code></p>

<p><code>T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...</code></p>

<p>again, using the power series expansion (done with <a href="http://www.wolframalpha.com/input/?i=%281+-+sqrt%281-4x%29%29+%2F+%282x%29" rel="noreferrer">Wolfram Alpha</a>). This expresses the non-obvious (to me) fact that there is only one binary tree with 1 element, 2 binary trees with two elements (the second element can be on the left or the right branch), 5 binary trees with three elements etc.</p>

<p>So my question is - what am I doing here? These operations seem unjustified (what exactly is the square root of an algebraic data type anyway?) but they lead to sensible results. does the quotient of two algebraic data types have any meaning in computer science, or is it just notational trickery?</p>

<p>And, perhaps more interestingly, is it possible to extend these ideas? Is there a theory of the algebra of types that allows, for example, arbitrary functions on types, or do types require a power series representation? If you can define a class of functions, then does composition of functions have any meaning?</p>