Kontynuacja przejścia transformacji funkcji binarnych

Przypomnijmy transformację przechodzącą kontynuację (transformacja CPS), która przyjmuje do (gdzie jest ustalone) do zdefiniowane przez $A$ $\beta A \mathrel{{:}{=}} R^{R^A}$ $R$ $f : A \to B$ $\beta f : \beta A \to \beta B$ W rzeczywistości mamymonadę kontynuacyjnąz jednostką zdefiniowaną przez

β f κ r : = κ (r \circ f) .

$\beta \, f \, \kappa \, r \mathrel{{:}{=}} \kappa (r \circ f).$

η_{A} : A \to β A

$\eta_A : A \to \beta A$

i mnożenie

zdefiniowane przez

η_{A} x : = λ r . r x

$\eta_A x \mathrel{{:}{=}} \lambda r . r \, x$

μ_{A} : β (β A) \to β A

$\mu_A : \beta (\beta A) \to \beta A$

μ_{A} K r : = K (λ f . f r) .

$\mu_A \, K \, r \mathrel{{:}{=}} K (\lambda f . f \, r).$

Teraz zastanówmy się w jaki sposób możemy przekształcić binarne mapa , czyli chcemy . Szybko pojawia się $f : A \to B \to C$ $\gamma f : \beta A \to \beta B \to \beta C$ Ma to również sens z punktu widzenia programowania.

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

$\gamma \, f \, \kappa \, \nu \, r \mathrel{{:}{=}} \kappa (\lambda x . \beta (f x) \nu r).$

Oto moje pytanie: czy istnieje głębszy powód , inny niż fakt, że wygląda to właściwie z punktu widzenia programowania? Na przykład, czy istnieje uzasadnienie teoretyczne lub inne „teoretyczne” powody, by sądzić, że ma sens? Na przykład, czy możemy ugotować z monady w systematyczny sposób? $\gamma$ $\gamma$ $\gamma$

Szukam wglądu w transformacje CPS elementowych funkcji. $n$

— Andrej Bauer
źródło

Szukasz czegoś poza Haskellem liftM2lub uogólnieniami Applicative? Możesz uzyskać n-aryjską wersję tego, co opisujesz (w języku, który pozwala mówić o n-ary funkcjach polimorficznych) bezpośrednio ze struktury aplikacyjnej kontynuacji.

— copumpkin

Wiem, jak napisać te uogólnienia, chcę wiedzieć, dlaczego takie są. Teoretycy kategorii zrozumieją, o co proszę.

— Andrej Bauer,

ApplicativeliftA2

γ

$\gamma$

Tak, liftA2było częścią tego, co sugerowałem. Pojęcie „idiom nawias” ( (| f x y z ... |)przekłada się na pure f <*> x <*> y <*> z <*> ...) Applicativewydaje się systematycznym sposobem na uzyskanie n-arytycznej formy twojego pytania. Znam CT, ale wydawało się, że najłatwiej jest o tym mówić w standardowych terminach programowania. Jeśli jeszcze tego nie spotkałeś Applicative, możesz przyjrzeć się luźnym funktorom monoidalnym (chociaż wypowiedź Haskella o tym <*>zawiera również wykładnicze). W każdym razie nie mam dla ciebie odpowiedzi, ale starałem się lepiej zrozumieć, o co ci chodzi :)

— copumpkin

Praca doktorska Hayo Thielecke dotyczy kategorycznej struktury CPS. Może odpowiedź leży tam lub w innych jego publikacjach. cs.bham.ac.uk/~hxt/research/hayo-thielecke-publications.shtml

— Dave Clarke

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

\neg \neg A \otimes \neg \neg B ⟶ \neg \neg (A \otimes B)

$\neg\neg A \otimes \neg\neg B \longrightarrow \neg\neg(A \otimes B)$

$\kappa\wedge$ $\epsilon$

— Noam Zeilberger
źródło

Zwiększenie odpowiedzi Noama:

$f : A \to B \to C$ $uncurry( f) : A \times B \to C$ $T$ $dblstr : T A \times T B \to T (A\times B)$

$T A \times T B \xrightarrow {dblstr} T(A\times B) \xrightarrow{uncurry(f)} TC$

Jeśli utworzymy instancję monady kontynuacyjnej, uzyskamy twoją konstrukcję.

$n$

$\pi$ $n$ $\pi$ $str_{\pi} : T A_1 \times \cdots \times T A_n \to T(A_1 \times \cdots \times A_n)$ $n$ $f : A_1 \times \cdots \times A_n \to C$ $\gamma f : TA_1 \times \cdots \times TA_n \xrightarrow{str_{\pi}} T(A_1 \times \cdots \times A_n) \xrightarrow{Tf} TC$

Ale nadal nie sądzę, że to naprawdę daje odpowiedź, której szukasz ...

— Ohad Kammar
źródło