3 ms·
The universal algebra perspective on monads is that m x is the set of expressions (ie. ASTs) for a particular algebraic structure with variables drawn from the
by edflsafoiewq 9y ago
The universal algebra perspective on monads is that m x is the set of expressions (ie. ASTs) for a particular algebraic structure with variables drawn from the set x. For example, you have a monad for abelian groups where the expressions are things like a+b, 2a-b, 1. Note that m encodes both the operations of the algebraic structure, like +, and the laws that they obey, because we regard a+b and b+a to be the same AST (ie. these are considered equal as a matter of syntax).
A concrete algebraic structure is a map m x -> x that evaluates expressions, producing their value, eg. 7+3 -> 10. It essentially provides concrete definitions for the syntactic operations in the ASTs.
Under this interpretation, the monad operations say "a bare value is an expression, eg. a, b" (x -> m x) and "nested expressions can be simplified, eg. (a+b)+(c) = a+b+c") (m m x -> m x). The monad laws essentially are ensuring that no matter what order you evaluate subexpressions and simply an expression, it always comes out to the same value in the end. It essentially lets us state a Church–Rosser theorem for the maps m x -> x.
- superlopuh 9y agoThat's pretty neat. Can you recommend a resource to read up on this a bit more?
- edflsafoiewq 9y agoNot really. You can see the basic idea on the nLab: https://ncatlab.org/nlab/show/variety+of+algebras#free_algebras https://ncatlab.org/nlab/show/variety+of+algebras#free_algeb... Continuing the example I gave, the monad law "Identity" says that "trivial subexpressions are already simplified" a+b = (a)+(b) || || (a+b) = a+b and the monad law "Associativity" says that "order of simplification doesn't matter" ((a)+(b))+((c+d)+(e)) = (a)+(b)+(c+d)+(e) || || (a+b)+(c+d+e) = a+b+c+d+e The laws for an algebra for a monad say "Trivial expressions evaluate to themselves" a = (a) = a and "you get the same result no matter the order you do evaluations and simplifications" (6+1)+(3) = 7+3 || || 6+1+3 = 10