FT EDSL 中的 Y 组合器
我正在尝试弄清楚如何在 Final Tagless EDSL 中表达 Y-Combitor：
class Symantics exp where
lam :: (exp a -> exp b) -> exp (exp a -> exp b)
app :: exp (exp a -> exp b) -> exp a -> exp b
fix :: ...
fix f = .....
我不确定，但我认为 Y-Combinator 的默认实现应该可以使用“lam”和“app”。
有人知道怎么做吗？我的第一次尝试失败了，因为“无法构造无限类型”。
干杯， 冈瑟
I'm trying to figure out how to express the Y-Combitor in this Finally Tagless EDSL:
class Symantics exp where
lam :: (exp a -> exp b) -> exp (exp a -> exp b)
app :: exp (exp a -> exp b) -> exp a -> exp b
fix :: ...
fix f = .....
I'm not certain but I think a default implementation of the Y-Combinator should be possible using "lam" and "app".
Anybody know how? My first attempts fail because of the "cannot construct the infinite type" thingy.
Cheers,
Günther
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果引入let，则可以提供默认实现。但是你不能单独使用 lam 和 app 来做到这一点，出于同样的原因，你不能在没有 let 的情况下直接在 Haskell 中编写它。这里您的目标是简单类型 lambda 演算的扩展，并且该术语不会在其中键入。
If you introduce let, you can provide a default implementation. But you can't do so with lam and app alone, for the same reason you can't write it directly in Haskell without let. Your target here is an extension of the simply typed lambda calculus, and that term just won't type in it.
正如 sclv 指出的那样，您需要在语言中引入原始定点形式。想想它是如何在 Haskell 中定义的：
合适的“let”绑定形式将帮助您实现这一点。 Barendregt 第 1 章和第 2 章是这类基础知识的一个很好的参考资料，它们可能在您的图书馆中——尽管我相信它已经绝版了（有人能确认吗？）。紧随其后的是 http://citeseerx.ist.psu。 edu/viewdoc/summary?doi=10.1.1.46.9283
As sclv points out, you'll need to introduce a primitive fixed point form into the language. Think about how it is defined in Haskell:
A suitable 'let' binding form will get you there. A good reference for this kind of foundational stuff is Barendregt chapters 1 and 2, which might be at your library -- though I believe it is out of print (can anyone confirm?). A close second is http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.9283