I know that:
- Binary leaf trees are free magmas.
- Non-empty lists are free semigroups.
- Lists are free monoids.
- The generalized algebraic datatype
data FM a where {Return::a->FM a; Bind::FM b -> (b->FM a) -> FM a}
is a free monad.
I know also that various abstract datatypes also correspond to free structures—bags are free commutative monoids and finite sets are free commutative idempotent monoids.
Do other algebraic datatypes (e.g., Maybe
, or 2-3 trees, or binomial trees) also correspond to free algebraic structures? If so, how might those be characterized?