What is the relationship between the equation of combinatorial species $L=1+XL$ and the similar one of data types, and how could it be generalized

Question

In several places (for example here) I have seen a comparison made between

• The equation of combinatorial species $L = 1 + XL$ where $L$ is the species of linear orders and $X$ is the species of "elements"
• The equation of algebraic data types $L(x) = 1 + x L(x)$ where $L(x)$ is the type of lists of elements of the type $x$

However, I don't understand the comparison, because:

• The concept of a linear order on a set is completely different than the concept of a list of elements of a set. A list is allowed to be any length, have duplicates, etc. But a linear order on $S$ must be the same length as $S$ and must list each element once.
• The addition and multiplication operations on combinatorial species seem completely different in nature to those operations as they are defined on algebraic data types. For example, the "$x L(x)$" in the equation of data types means "an element of a set and a list of elements of the same set", whereas the "$XL$" in in the equation of species means "first partition a set into two sets and then do two different things with the two different sets".
• The analogy doesn't seem to extend to other equations of species. For example, the same document I linked to above gives the example of $S = E \cdot \mathrm{Der}$ where $S$ is the species of permutations, $E$ is the species of "sets", and $\mathrm{Der}$ the species of "derangements". But there doesn't seem to be any way to interpret that as a corresponding identity of data types, as far as I can tell. For example, it could be interpreted as "to pick a permutation on a set, first pick [something] and then pick a a derangement on the set", but there is no "[something]" that would make that sentence true.

So my question is, what is the actual connection between these equations, and how would it generalize to other equations of species?

Answer 1

The comparison is that linear orders are isomorphic to lists of elements of type $1$ (the type which has a single element). The "set" in "linear order on a set" and "list of elements of a set" are two different sets. It is the simplest possible comparison: there is a unique linear order of size $n$, and it corresponds to the unique list of $n$ identical things.