问题标签 [letrec]

我正在尝试使用函数的数学 lambda 表示法来实现 letrec，但我遇到了困难。我的任务说 let 可以定义为

并且 letrec 可以定义为

我已经成功实现了 let 以在表达式中查找 freevars，但我正在努力实现 letrec：

有人可以指导我如何做到这一点吗？我必须使用 Lambda 吗？在这一点上我很迷茫，只是试图遵循定义的实现对我来说一定是错误的，因为我不能让它工作。

我已经查看了我能找到的关于 letrec 的所有内容，但我仍然不明白它给语言带来了什么特性。似乎所有可以用 letrec 表达的东西都可以很容易地写成递归函数。但是，如果语言已经支持递归函数，是否有任何理由将letrec 公开为编程语言的一个特性？为什么几种语言都暴露了两者？

我知道 letrec 可能用于实现其他功能，包括递归函数，但这与为什么它本身应该是一个功能无关。我还读到有些人发现它比某些 lisps 中的递归函数更具可读性，但这又无关紧要，因为语言的设计者可以努力使递归函数具有足够的可读性，不需要其他功能。最后，有人告诉我 letrec 可以更简洁地表达某些递归值，但我还没有找到一个激励的例子。

据我了解，以下内容：let、、let*和是 Scheme/Racketletrec中letrec*使用的合成糖。

现在，如果我有一个简单的程序：

它被翻译成：

如果我有：

它被翻译成：

现在，对于我的第一个问题，我理解了letrec表达式的含义，它使人们能够在 let 中使用递归，但我不明白它是如何完成的。letrec翻译成什么？

例如，会发生什么

被翻译成？

第二个问题与letrec*- 但letrec*我不明白它到底有什么不同letrec？还有，一个letrec*表达式会被翻译成什么？

这是 Haskell 中定点组合器的通常定义：

在https://wiki.haskell.org/Prime_numbers上，他们定义了一个不同的定点组合器：

_Y是一个非共享定点组合器，在这里安排一个递归的“伸缩”多级素数生产（生产者塔）。

这到底是什么意思？在这种情况下，什么是“共享”与“非共享”？与有何_Y不同？fix

我想了解let绑定在 Haskell 中是如何工作的（或者可能是 lambda 演算，如果 Haskell 实现不同？）

我从阅读Write you a Haskell中了解到，这对单个let绑定有效。

这对我来说很有意义，因为它与绑定在 lambda 演算中的工作方式是一致的。我感到困惑的是使用多个let绑定，其中一个绑定可以引用上面的绑定。我将提供一个简单的例子。

原始代码：

我对实现的猜测：

这似乎不起作用，因为times在 lambda 调用 square 时未定义。然而，这可以通过这个实现来解决：

这是实现此绑定的正确方法，至少在 lambda 演算中是这样吗？

我必须从中提取用户名和电子邮件Either。AuthResponse

我case of为它使用构造：

但我对两者都有这个uname警告uemail：

我希望这let (uname, uemail)超出了case of块的范围。

如果并且尚未定义，如何从case块中获得此警告？unameuemail

以下组合器以创造性（有人会说滥用）方式使用默认参数，它的行为有点像 Scheme 的letrec*：

^{* 如果我错了，请纠正我，我不太了解Scheme}

它有效，但bind没有类型。接下来我尝试手动对上述main函数进行编码：

它可能有效，但它是可怕的。如何避免嵌套？我玩过fix递归，但我不知道如何以这种方式表达闭包：

是否有一种递归算法可以有效地创建闭包或本地绑定，以便当前绑定可能依赖于以前的绑定？

我正在阅读Friedman 和 Felleisen的 The Seasoned Schemer，但我对他们的一些最佳实践感到有些不安。作者特别推荐：

• 用于letrec删除对于递归应用程序不会更改的参数；
• 用于letrec隐藏和保护功能；
• 用于letcc突然而迅速地返回值。

让我们来看看这些规则的一些后果。例如，考虑以下用于计算列表列表交集的代码：

这个例子出现在第 13 章（不完全像这样：我粘贴了在前一段中单独定义的成员资格测试代码）。

我认为以下替代实现，它的使用非常有限，letrec并且letcc更具可读性和更易于理解：

我是方案新手，我的背景不是计算机科学，但令我震惊的是，对于一个简单的列表交集问题，我们必须得到如此复杂的代码。这让我想知道人们如何管理现实世界应用程序的复杂性。经验丰富的策划者是否每天都在深度嵌套letcc和letrec表达？

这是询问 stackexchange 的动机。

我的问题是：Friedman 和 Felleisen 是否为了教育而过度复杂化了这个示例，还是出于性能原因我应该习惯于使用充满letccs 和s 的方案代码？letrec对于大型列表，我的幼稚代码是否会变得不切实际？

我试图通过比较其他函数式编程语言和概念中的类似功能来了解递归集如何在内部运行。

我可以在wiki中找到它。在那，我需要知道 Y 组合子，不动点。我可以在wiki中简要了解它。

然后，现在我开始在 Haskell 中应用它。

哈斯克尔

这很容易。但我想知道幕后。

我正在为一种小表达式语言编写一个评估器，但我被困在这个LetRec结构上。

这是语言：

到目前为止，这是评估员：

这是我要评估的测试功能：