Re:Monads for functional programming (1995) [pdf]
by superlopuh on Sunday May 06, 2018 @06:06PM
(#17008861)
That's pretty neat. Can you recommend a resource to read up on this a bit more?
Re:Monads for functional programming (1995) [pdf]
by edflsafoiewq on Sunday May 06, 2018 @07:01PM
(#17009137)
Not really. You can see the basic idea on the nLab: 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
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.