1
$\begingroup$

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?

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.