Монада-трансформатор

В функциональном программировании преобразователь монад — это конструктор типов, который принимает монаду в качестве аргумента и возвращает монаду в качестве результата.

Трансформаторы монад могут использоваться для составления функций, инкапсулированных монадами, такими как состояние, обработка исключений и ввод-вывод, модульным способом. Обычно трансформер монад создается путем обобщения существующей монады; применение полученного трансформера монады к монаде идентичности дает монаду, которая эквивалентна исходной монаде (игнорируя любую необходимую упаковку и распаковку).

Определение

Монадный трансформатор состоит из:

1. Конструктор tтипа​ (* -> *) -> * -> *
2. Операции монад returnи bind(или эквивалентная формулировка) для всех t m, где mесть монада, удовлетворяющая законам монады
3. Дополнительная операция, lift :: m a -> t m a, удовлетворяющая следующим законам: ^[1] (обозначение `bind`ниже указывает на инфиксное применение):
   1. lift . return = return
   2. lift (m `bind` k) = (lift m) `bind` (lift . k)

Примеры

Опциональный монада-трансформер

Для любой монады трансформатор монады опций (где обозначает тип опции ) определяется следующим образом: ${\displaystyle \mathrm {M} \,A}$ ${\displaystyle \mathrm {M} \left(A^{?}\right)}$ ${\displaystyle A^{?}}$

${\displaystyle {\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{return Nothing}}&{\mbox{if }}a=\mathrm {Nothing} \\f\,a'&{\mbox{if }}a=\mathrm {Just} \,a'\end{cases}}\right)\\\mathrm {lift} :&\mathrm {M} (A)\rightarrow \mathrm {M} \left(A^{?}\right)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} (\mathrm {Just} \,a))\end{array}}}$

Исключение монадного трансформатора

Для любой монады преобразователь монад исключений (где E — тип исключений) определяется следующим образом: ${\displaystyle \mathrm {M} \,A}$ ${\displaystyle \mathrm {M} (A+E)}$

${\displaystyle {\begin{array}{ll}\mathrm {return} :&A\rightarrow \mathrm {M} (A+E)=a\mapsto \mathrm {return} (\mathrm {value} \,a)\\\mathrm {bind} :&\mathrm {M} (A+E)\rightarrow (A\rightarrow \mathrm {M} (B+E))\rightarrow \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 {value} \,a'\end{cases}}\right)\\\mathrm {lift} :&\mathrm {M} \,A\rightarrow \mathrm {M} (A+E)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} (\mathrm {value} \,a))\\\end{array}}}$

Читатель-трансформатор монады

Для любой монады преобразователь монады читателя (где E — тип среды) определяется следующим образом: ${\displaystyle \mathrm {M} \,A}$ ${\displaystyle E\rightarrow \mathrm {M} \,A}$

${\displaystyle {\begin{array}{ll}\mathrm {return} :&A\rightarrow E\rightarrow \mathrm {M} \,A=a\mapsto e\mapsto \mathrm {return} \,a\\\mathrm {bind} :&(E\rightarrow \mathrm {M} \,A)\rightarrow (A\rightarrow E\rightarrow \mathrm {M} \,B)\rightarrow E\rightarrow \mathrm {M} \,B=m\mapsto k\mapsto e\mapsto \mathrm {bind} \,(m\,e)\,(a\mapsto k\,a\,e)\\\mathrm {lift} :&\mathrm {M} \,A\rightarrow E\rightarrow \mathrm {M} \,A=a\mapsto e\mapsto a\\\end{array}}}$

Трансформатор монады состояния

Для любой монады трансформатор монады состояния (где S — тип состояния) определяется следующим образом: ${\displaystyle \mathrm {M} \,A}$ ${\displaystyle S\rightarrow \mathrm {M} (A\times S)}$

${\displaystyle {\begin{array}{ll}\mathrm {return} :&A\rightarrow S\rightarrow \mathrm {M} (A\times S)=a\mapsto s\mapsto \mathrm {return} \,(a,s)\\\mathrm {bind} :&(S\rightarrow \mathrm {M} (A\times S))\rightarrow (A\rightarrow S\rightarrow \mathrm {M} (B\times S))\rightarrow S\rightarrow \mathrm {M} (B\times S)=m\mapsto k\mapsto s\mapsto \mathrm {bind} \,(m\,s)\,((a,s')\mapsto k\,a\,s')\\\mathrm {lift} :&\mathrm {M} \,A\rightarrow S\rightarrow \mathrm {M} (A\times S)=m\mapsto s\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} \,(a,s))\end{array}}}$

Писатель монада трансформатор

Для любой монады преобразователь монады писателя (где W наделен моноидной операцией ∗ с элементом идентичности ) определяется следующим образом: ${\displaystyle \mathrm {M} \,A}$ ${\displaystyle \mathrm {M} (W\times A)}$ ${\displaystyle \varepsilon }$

${\displaystyle {\begin{array}{ll}\mathrm {return} :&A\rightarrow \mathrm {M} (W\times A)=a\mapsto \mathrm {return} \,(\varepsilon ,a)\\\mathrm {bind} :&\mathrm {M} (W\times A)\rightarrow (A\rightarrow \mathrm {M} (W\times B))\rightarrow \mathrm {M} (W\times B)=m\mapsto f\mapsto \mathrm {bind} \,m\,((w,a)\mapsto \mathrm {bind} \,(f\,a)\,((w',b)\mapsto \mathrm {return} \,(w*w',b)))\\\mathrm {lift} :&\mathrm {M} \,A\rightarrow \mathrm {M} (W\times A)=m\mapsto \mathrm {bind} \,m\,(a\mapsto \mathrm {return} \,(\varepsilon ,a))\\\end{array}}}$

Продолжение монадного трансформатора

При наличии любой монады трансформатор монады продолжения отображает произвольный тип R в функции типа , где R — тип результата продолжения. Он определяется следующим образом: ${\displaystyle \mathrm {M} \,A}$ ${\displaystyle (A\rightarrow \mathrm {M} \,R)\rightarrow \mathrm {M} \,R}$

${\displaystyle {\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\rightarrow \mathrm {M} \,R\right)\rightarrow \mathrm {M} \,R\right)\rightarrow \left(A\rightarrow \left(B\rightarrow \mathrm {M} \,R\right)\rightarrow \mathrm {M} \,R\right)\rightarrow \left(B\rightarrow \mathrm {M} \,R\right)\rightarrow \mathrm {M} \,R=c\mapsto f\mapsto k\mapsto c\,\left(a\mapsto f\,a\,k\right)\\\mathrm {lift} \colon &\mathrm {M} \,A\rightarrow (A\rightarrow \mathrm {M} \,R)\rightarrow \mathrm {M} \,R=\mathrm {bind} \end{array}}}$

Обратите внимание, что преобразования монад обычно не являются коммутативными : например, применение преобразователя состояний к монаде опций дает тип (вычисление, которое может завершиться неудачей и не дать конечного состояния), тогда как обратное преобразование имеет тип (вычисление, которое дает конечное состояние и необязательное возвращаемое значение). ${\displaystyle S\rightarrow \left(A\times S\right)^{?}}$ ${\displaystyle S\rightarrow \left(A^{?}\times S\right)}$

Смотрите также

• Монады в функциональном программировании

Ссылки

1. Лян, Шэн; Худак, Пол; Джонс, Марк (1995). «Трансформаторы монад и модульные интерпретаторы» (PDF) . Труды 22-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . Нью-Йорк, Нью-Йорк: ACM. стр. 333–343. doi : 10.1145/199448.199528 .

Внешние ссылки

• Высокотехническая запись в блоге, в которой кратко рассматривается часть литературы по монадным трансформаторам и связанным с ними концепциям, с акцентом на категориально-теоретическое рассмотрение.