On 7/24/11 10:09 PM, Sebastian Fischer wrote:
because list is a (the?) free monoid.
Yes, all free monoids are isomorphic (to lists).
Sebastian
For completeness... The free monoid over a set S is the set of all finite sequences of elements drawn from S. Often this is written with the Kleene star: S^*. Finite lists are a particular representation for the free monoid (namely with all operations associated to the right), though this representation may not be "isomorphic enough" for certain analyses (e.g., algorithmic complexity). Note that the free semigroup over a set S is the set of all finite non-empty sequences of elements drawn from S. We can name this by S^+. Other than the fact that S^+ does not contain the empty sequence, the other important difference is that, while both S^* and S^+ are both closed under the operation, only S^* is co-closed under the operation (i.e., not all elements of S^+ can be decomposed into two elements of S^+ joined by the operator). -- Live well, ~wren