我在fixana这里有这个可爱的功能，它的执行速度比她姐姐快 5 倍ana。（我有一份criterion报告支持我）

我可以cata用同样的方式表达他们的表弟吗？

在我看来，我做不到，但过去我曾多次被我的 SO 伙伴羞辱过。

我的意思是，从定义来看：

fix f是函数的最小不动点f

换句话说：

最小的定义x使得f x = x.

任何空值类型的最少定义值是undefined。这里仍然存在一些歧义，undefined可能意味着“将引发错误”（更好）或“永远不会终止”（更糟）。正如推理和试验所表明的那样，fix (+1)两者fix pred :: Word似乎都从未接近终止（即使pred 0是一个错误），所以“永不终止”中最糟糕的一个很可能总是在这两种选择之间被选择。（能逃脱fix的就是无聊const 1，以后再说吧。）

这不是有用的申请方式fix。

有用的应用方式fix是：

-- 即使用fix来神奇地产生一个递归函数。（这总是让我感到惊讶。）这可以被视为在 2 个函数之间进行选择：\f x -> f (x - 1)和\_ x -> x，其中一个永远不会评估其第一个绑定变量。这是一个危险的玩具，因为我们仍然可以很容易地获得一个在其一半域内不终止的函数，就像意外翻转>到<或-to一样容易+。

所以，不知何故，这两个功能：

-- 后者是“最少定义的”。如果我们用力眯起眼睛，我们实际上可以认出我们无聊的家伙const，只是flip'd。

现在，这是违反直觉的。f2实际上更具容错性，因此从某种意义上说，它被定义为比f1. （特别是，这是让它逃脱否则无限循环的原因fix）。具体来说，f2为所有相同(f, x)的输入对定义为f1加上(undefined, x). 同样，const 1是所有一元函数中容错能力最强的。

那么，我现在如何理解定义性？

这个问题的一些理由

附近有这个答案fix，它提供了与这个问题中提出的不同的直觉。它还强调，为了全面理解，必须通过关于指称语义的外部教程。

我想得到一个答案，要么支持，要么解释这里提出的直觉的错误，而且，如果领域理论真的是评论中提出的草书顺序的背后，至少包括一些经验法则，允许，不管多么有限，但领域理论的实际应用。我希望看到的问题的一个特定部分是一个有fix能力的函数是否总是可以分解为一个常量函数和一个归约函数，以及这些函数类的定义是什么。

我的愿望是在可靠的数学推理的支持下，就构建有用且安全fix的编码递归提供一个实际的、实用的答案。

我在思考延迟评估的工作原理时遇到了一些问题。我试图用 Y-Combinator 来理解它：

如果我们编写一个简单版本的 Y-Combinator，我们会遇到无限递归的问题：

当我们构建一个递归函数时，问题就出现了：

Ysimple = (lambda f : (lambda x : f(x(x))) (lambda x : f(x(x)) ))
[上一行重复了 995 次以上] RecursionError: 超出最大递归深度

但是我们可以将第二个或两个 -f(x(x))表达式包装在延迟抽象中：

现在代码工作得很好。但为什么？

如果我们只有Ysimple在我们的文件中，则不会评估任何内容。所以我假设只有 lambdas 被评估为顶级表达式。

我做了一些手动评估步骤，但我没有看到延迟发生的原因：

延迟发生在哪里？在这两种情况下F都是顶级表达式，并且在这两种情况下lambda x都在 level below F。延迟起什么作用lambda y？

编辑：

同样，为什么延迟在这里的第一行是如何工作的：

我正在努力在 Haskell 中创建一个 AST。我想添加不同的注释，例如类型和位置信息，所以我最终使用了fixplate。但是，我在网上找不到任何示例并且遇到了一些困难。

我已经按照 fixplate 的建议设置了我的 AST（有些被删除了）：

接下来添加一个标签，我创建了另一种类型，以及一个基于树遍历添加标签的函数。

但是，除此之外，我遇到了一些问题。例如，我正在尝试编写一个对 AST 进行一些转换的函数。因为它需要一个标签才能运行，所以我制作了 type LabelProgram -> Program，但我认为我在这里做错了。下面是部分函数的片段（其中一个更简单的部分）：

我觉得我在这里工作的抽象级别错误。我应该像这样显式匹配Fix Ann ...并返回Fix ...，还是我使用了错误的固定板？

此外，我担心如何泛化函数。如何使我的函数一般适用于Programs、LabelPrograms 和TypePrograms？

我想只使用这种类型定义来定义列表：

我成功地定义了自然数，如下所示：

我知道如何借助额外的数据类型来定义列表：

我能得到的“更好”是这样，但它不进行类型检查（预期类型是 µL.(1+(a*L))）：

如何仅定义nilMu和consMu使用先前定义的类型及其构造函数？

编辑

正如@chi answer解释的那样，可以定义 anewtype如下：

它进行类型检查，但需要定义一个新类型。

这个问题的目的是用单位、乘积、总和和递归类型扩展一个简单类型的组合逻辑。前三种类型很容易实现，引入了 7 个新的组合子（unit, pair, first, second, left, right, case）。递归类型似乎也很容易实现，只需添加一个类型构造函数组合器mu，但正如这个问题所示，如果没有额外的语言构造，它就不够灵活。

这个问题有解决方案吗？是否有递归类型的组合逻辑可供参考？

我尝试使用 y-combinator（在 Lua 和 Clojure 中），因为我认为这将允许我在使用递归时超出默认堆栈实现的大小。看来我弄错了。是的，它有效，但是在这两个系统中，堆栈的崩溃与使用普通的旧递归完全相同。Clojure 中的低约 3600 和我的 Android Lua 实现中的高约 333000。它也比常规递归慢一点。

那么使用 y-combinator 有什么好处，还是只是为了证明一个观点而进行的智力练习？我错过了什么吗？

===

PS。抱歉，我应该更清楚地说明我知道我可以使用 TCO 来超过堆栈。我的问题与此无关。我对此很感兴趣 a) 从学术/知识的角度来看 b) 是否可以对那些不能递归编写的函数做任何事情。

我想为Show以下类型的列表编写一个实例：

Module Data.Functor.Foldable定义了它，但它将它转换为Fix，这是我想避免的。

我该如何定义这个Show实例？

由于Nothing >>= f = Nothing对于 every f，以下简单定义适用于mfix：

但这没有实际用途，因此我们有以下非全定义：

如果这个- 子句不会停止，如果mfix f返回就好了。（例如，） 这是不可能的，因为停机问题是无法解决的吗？Nothingletf = Just . (1+)

在像 Haskell 这样的惰性非全语言中，最小固定点如何与最大固定点重合。完全部分订单的连续性与此有什么关系？

loop来自的说明Control.Arrow：

循环运算符表示将输出值作为输入反馈的计算，尽管计算只发生一次。它是箭头符号中的 rec 值递归结构的基础。

它的源代码，以及它的实例化(->)：

这立即让我想起fix了定点组合器：

所以我的问题是：

1. 是否有可能实现那个特定的loopvia fix？
2. 它们的功能有何不同？