Продолжение прохождения преобразования двоичных функций

13

Вспомните преобразование прохождения продолжения (преобразование CPS), которое переводит в (где фиксировано) и до определяется как На самом деле у нас есть монада продолжения с единицей определенной как и умножение определяемое как β A : = R R A R f : A B β f : β A β B βAβA:=RRARf:ABβf:βAβB

βfκr:=κ(rf).
η A x : = λ r . рηA:AβAμ A : β ( β A ) β A μ A
ηAx:=λr.rx
μA:β(βA)βA
μAKr:=K(λf.fr).

Теперь давайте подумаем о том , как мы можем преобразовать двоичное отображение , то есть, мы хотим . Один быстро приходит с Это имеет смысл и с точки зрения программирования.f:ABCγf:βAβBβC

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

Вот мой вопрос: есть ли более глубокая причина для γ , кроме того факта, что она выглядит правильно с точки зрения программирования? Например, есть ли теоретико-категорийная или другая «теоретическая» причина для размышления о том, что γ имеет смысл? Например, можем ли мы приготовить γ из монады систематическим способом?

Я ищу понимание преобразований CPS n -арных функций.

Андрей Бауэр
источник
2
Вы ищете что-то помимо Хаскелла liftM2или обобщений Applicative? Вы можете получить n-арную версию того, что вы описываете (на языке, который позволяет говорить о n-арных полиморфных функциях) непосредственно из аппликативной структуры продолжения.
copumpkin
1
Я знаю, как написать эти обобщения, я хочу знать, почему они такие. Теоретики категорий поймут, о чем я спрашиваю.
Андрей Бауэр
1
Хм, спасибо за указание Applicative. У меня есть liftA2это , см. Hackage.haskell.org/packages/archive/base/4.2.0.0/doc/html/…γ
Андрей Бауэр
3
Да, liftA2было частью того, что я предлагал. Понятие «идиоматическая скобка» (в (| f x y z ... |)переводе на pure f <*> x <*> y <*> z <*> ...) Applicativeвыглядит как систематический способ получить n-арную форму вашего вопроса. Я знаю CT, но казалось, что проще всего говорить об этом в стандартных терминах программирования. Если вы раньше не сталкивались Applicative, возможно, вы захотите взглянуть на слабые моноидальные функторы (хотя утверждение Хаскелла об этом также <*>включает в себя экспоненты). В любом случае, у меня нет ответа для вас, но я пытался лучше понять, к чему вы
клонили
2
Кандидатская диссертация Хайо Тилеке посвящена категориальной структуре CPS. Может быть, ответ лежит там или в других его публикациях. cs.bham.ac.uk/~hxt/research/hayo-thielecke-publications.shtml
Дейв Кларк

Ответы:

7

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

¬¬A¬¬B¬¬(AB)

κϵ

Ноам Цайлбергер
источник
4

Увеличивая ответ Ноама:

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

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

Если мы создадим это в монаде продолжения, мы получим вашу конструкцию.

n

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

Но я все еще не думаю, что это действительно дает вам ответ, который вы ищете ...

Охад Каммар
источник