Continuación pasando transformada de funciones binarias

13

Recordemos la transformación de paso de continuación (transformación CPS) que lleva a β A : = R R A (donde R está fijo) yf : A B a β f : β A β B definido por βAβA:=RRARf:ABβf:βAβB De hecho, tenemos lamónada de continuacióncon la unidad η A : A β A definida por η A x : = λ r . r

βfκr:=κ(rf).
ηA:AβA y la multiplicación μ A : β ( β A ) β A definido por μ A
ηAx:=λr.rx
μA:β(βA)βA
μAKr:=K(λf.fr).

Ahora vamos a pensar acerca de cómo podemos transformar una binaria mapa , es decir, queremos γ f : β A β B β C . A uno se le ocurre rápidamente γf:ABCγf:βAβBβC Esto también tiene sentido desde el punto de vista de la programación.

γfκνr:=κ(λx.β(fx)νr).

Aquí está mi pregunta: ¿hay una razón más profunda para , además del hecho de que se ve bien desde el punto de vista de la programación? Por ejemplo, ¿hay una razón teórica de categoría u otra razón "teórica" ​​para pensar que γ tiene sentido? Por ejemplo, ¿podemos cocinar γ de la mónada de manera sistemática?γγγ

Estoy buscando una idea de las transformaciones CPS de las funciones -ary.n

Andrej Bauer
fuente
2
¿Estás buscando algo más allá de Haskell liftM2o generalizaciones Applicative? Puede derivar una versión n-aria de lo que describe (en un lenguaje que le permite hablar sobre funciones polimórficas n-arias) directamente de la estructura aplicativa de continuación.
copumpkin
1
Sé cómo escribir estas generalizaciones, quiero saber por qué son así. Los teóricos de la categoría entenderán lo que estoy preguntando.
Andrej Bauer el
1
Hmm, gracias por señalarlo Applicative. Tiene liftA2cuál es mi , consulte hackage.haskell.org/packages/archive/base/4.2.0.0/doc/html/…γ
Andrej Bauer el
3
Sí, liftA2era parte de lo que estaba sugiriendo. La noción de "soporte idiomático" ( (| f x y z ... |)traducido a pure f <*> x <*> y <*> z <*> ...) Applicativeparece ser la forma sistemática de obtener la forma n-ary de su pregunta. Conozco el CT, pero me pareció más simple hablar sobre él en términos de programación estándar. Si no se hubiera encontrado Applicativeantes, es posible que desee ver los functores monoidales laxos (aunque la declaración de Haskell sobre esto también <*>involucra exponenciales). De todos modos, no tengo una respuesta para ti, pero estaba tratando de entender mejor a qué te
referías
2
La tesis doctoral de Hayo Thielecke está en la estructura categórica de CPS. Quizás la respuesta se encuentre allí o en sus otras publicaciones. cs.bham.ac.uk/~hxt/research/hayo-thielecke-publications.shtml
Dave Clarke

Respuestas:

7

~~ A * ~~ B | - ~~ (A * B)

¬¬A¬¬B¬¬(AB)

κϵ

Noam Zeilberger
fuente
4

Aumentando la respuesta de Noam:

f:ABCuncurry(f):A×BCTdblstr:TA×TBT(A×B)

TA×TBdblstrT(A×B)uncurry(f)TC

Si instanciamos esto a la mónada de continuación, obtenemos su construcción.

n

πnπstrπ:TA1××TAnT(A1××An)nf:A1××AnCγf:TA1××TAnstrπT(A1××An)TfTC

Pero todavía no creo que esto realmente te dé la respuesta que estás buscando ...

Ohad Kammar
fuente