Monad transformator

I funktionell programmering är en monadtransformator en typkonstruktor som tar en monad som ett argument och returnerar en monad som ett resultat.

Monadtransformatorer kan användas för att komponera funktioner inkapslade av monader – såsom tillstånd, undantagshantering och I/O – på ett modulärt sätt. Vanligtvis skapas en monadtransformator genom att generalisera en existerande monad; applicering av den resulterande monadtransformatorn på identitetsmonaden ger en monad som är likvärdig med den ursprungliga monaden (bortse från eventuell nödvändig boxning och unboxning).

Definition

En monadtransformator består av:

1. En typkonstruktör av typen (* -> *) -> * -> *
2. Monadoperationer returnerar och binder (eller en likvärdig formulering) för alla tm där m är en monad, som uppfyller monadlagarna
3. En ytterligare operation, lift :: ma -> tma , som uppfyller följande lagar: (notationen 'bind' nedan anger infix-applikation):
   1. hiss . återvända = återvända
   2. lyfta (m `binda` k) = (lyfta m) `binda` (lyfta . k)

Exempel

Alternativet monad transformator

Givet någon monad $\mathrm {M} \,A$ , alternativet monadtransformator ${\displaystyle \mathrm {M} \left(A^{?}\right)} ($ där $A^{?}$ anger alternativtypen ) definieras av:

${\begin{array}{ll}\mathrm { return} :&A\rightarrow \mathrm {M} \left(A^{?}\right)=a\mapsto \mathrm {return} (\mathrm {Just} \,a)\\\mathrm {bind} :& \mathrm {M} \left(A^{?}\right)\rightarrow \left(A\rightarrow \mathrm {M} \left(B^{?}\right)\right)\rightarrow \mathrm {M} \left(B^{?}\right)=m\mapsto f\mapsto \mathrm {bind} \,m\,\left(a\mapsto {\begin{cases}{\mbox{retur Inget}}&{ \mbox{if }}a=\mathrm {Ingenting} \\f\,a'&{\mbox{if }}a=\mathrm {Bara} \,a'\end{cases}}\right)\\ \mathrm {lyft} :&\mathrm {M} (A)\högerpil \mathrm {M} \left(A^{?}\right)=m\mapsto \mathrm {bind} \,m\,(a\ mapsto \mathrm {return} (\mathrm {Bara} \,a))\end{array}}$

Undantaget monadtransformator

Givet alla monad ${\displaystyle \mathrm {M} \,A} ,$ undantaget monadtransformator ${\displaystyle \mathrm {M} (A+E)} ($ där E är typen av undantag ) definieras av:

${\begin{array}{ll }\mathrm {return} :&A\rightarrow \mathrm {M} (A+E)=a\mapsto \mathrm {return} (\mathrm {värde} \,a)\\\mathrm {bind} :&\mathrm {M} (A+E)\högerpil (A\högerpil \mathrm {M} (B+E))\högerpil \mathrm {M} (B+E)=m\mapsto f\mapsto \mathrm {bind} \ ,m\,\left(a\mapsto {\begin{cases}{\mbox{return err }}e&{\mbox{if }}a=\mathrm {err} \,e\\f\,a'& {\mbox{if }}a=\mathrm {värde} \,a'\end{cases}}\right)\\\mathrm {lift} :&\mathrm {M} \,A\högerpil \mathrm {M } (A+E)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} (\mathrm {värde} \,a))\\\end{array}}$

Läsaren monad transformator

Givet någon monad $\mathrm {M} \,A$ , är läsarmonadtransformatorn $E\rightarrow \mathrm {M} \,A$ (där E är miljötypen) definieras av:

${\begin{array}{ ll}\mathrm {retur} :&A\rightarrow E\rightarrow \mathrm {M} \,A=a\mapsto e\mapsto \mathrm {return} \,a\\\mathrm {bind} :&(E\rightarrow \mathrm {M} \,A)\högerpil (A\högerpil E\högerpil \mathrm {M} \,B)\högerpil E\högerpil \mathrm {M} \,B=m\mapsto k\mapsto e\mapsto \mathrm {bind} \,(m\,e)\,(a\mapsto k\,a\,e)\\\mathrm {lyft} :&\mathrm {M} \,A\högerpil E\högerpil \ mathrm {M} \,A=a\mapsto e\mapsto a\\\end{array}}$

Statens monadstransformator

Givet någon monad $\mathrm {M} \,A$ , tillståndsmonadtransformatorn ${\displaystyle S\rightarrow \mathrm {M} (A\times S)} ($ där S är tillståndstypen) definieras av:

${\begin{array}{ll }\mathrm {retur} :&A\rightarrow S\rightarrow \mathrm {M} (A\times S)=a\mapsto s\mapsto \mathrm {return} \,(a,s)\\\mathrm {bind} :&(S\högerpil \mathrm {M} (A\ gånger S))\högerpil (A\högerpil S\högerpil \mathrm {M} (B\gånger S))\högerpil S\högerpil \mathrm {M} ( B\ gånger S)=m\mapsto k\mapsto s\mapsto \mathrm {bind} \,(m\,s)\,((a,s')\mapsto k\,a\,s')\\ \mathrm {lyft} :&\mathrm {M} \,A\högerpil S\högerpil \mathrm {M} (A\ gånger S)=m\mapsto s\mapsto \mathrm {bind} \,m\,(a \mapsto \mathrm {return} \,(a,s))\end{array}}$

Författarmonadtransformatorn

Givet någon monad ${\displaystyle \mathrm {M} \,A} ,$ skrivmonadtransformatorn ${\displaystyle \mathrm {M} (W\ gånger A)} ($ där W är försedd med en monoid operation ∗ med identitetselement $\varepsilon$ ) definieras av:

${\begin {array}{ll}\mathrm {retur} :&A\rightarrow \mathrm {M} (W\ gånger A)=a\mapsto \mathrm {return} \,(\varepsilon ,a)\\\mathrm {bind} :&\mathrm {M} (W\ gånger A)\högerpil (A\högerpil \mathrm {M} (W\gånger B))\högerpil \mathrm {M} (W\ gånger B)=m\mapsto f\ mapsto \mathrm {bind} \,m\,((w,a)\mapsto \mathrm {bind} \,(f\,a)\,((w',b)\mapsto \mathrm {retur} \, (w*w',b)))\\\mathrm {lyft} :&\mathrm {M} \,A\högerpil \mathrm {M} (W\ gånger A)=m\mapsto \mathrm {bind} \ ,m\,(a\mapsto \mathrm {return} \,(\varepsilon ,a))\\\end{array}}$

Fortsättningsmonadtransformatorn

Givet någon monad ${\displaystyle \mathrm {M} \,A} ,$${\displaystyle (A\rightarrow \mathrm { M} \,R)\rightarrow \mathrm {M} \,R} ,$ fortsättningsmonadtransformatorn en godtycklig typ R till funktioner av typen där R är resultattypen för fortsättningen. Det definieras av:

${\begin{array}{ll}\mathrm {return} \colon &A\rightarrow \left(A\rightarrow \mathrm {M} \,R\right)\rightarrow \mathrm {M} \, R=a\mapsto k\mapsto k\,a\\\mathrm {bind} \colon &\left(\left(A\högerpil \mathrm {M} \,R\höger)\högerpil \mathrm {M} \ ,R\höger)\högerpil \left(A\högerpil \left(B\högerpil \mathrm {M} \,R\höger)\högerpil \mathrm {M} \,R\höger)\högerpil \left(B\ högerpil \mathrm {M} \,R\höger)\högerpil \mathrm {M} \,R=c\mapsto f\mapsto k\mapsto c\,\left(a\mapsto f\,a\,k\right )\\\mathrm {lyft} \colon &\mathrm {M} \,A\högerpil (A\högerpil \mathrm {M} \,R)\högerpil \mathrm {M} \,R=\mathrm {bind} \end{array}}$

Notera att monadtransformationer vanligtvis inte är kommutativa : till exempel, att applicera tillståndstransformatorn på alternativmonaden ger en typ $S\rightarrow \left(A\times S\right)^{?}$ (en beräkning som kan misslyckas och inte ger något sluttillstånd), medan den omvända transformationen har typen ${\ displaystyle S\rightarrow \left(A^{?}\times S\right)}$ (en beräkning som ger ett sluttillstånd och ett valfritt returvärde).

Se även

• Monader i funktionell programmering

externa länkar

• Ett mycket tekniskt blogginlägg som kort går igenom en del av litteraturen om monadtransformatorer och relaterade begrepp, med fokus på kategorisk-teoretisk behandling