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?



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.