Haskell/Fix 和递归
乍一看，fix 函数可能显得奇怪且无用。然而，它的存在有理论上的原因：将其作为原语引入 (类型化) lambda 演算 使你能够定义递归 函数。
fix 的定义很简单：
fix :: (a -> a) -> a
fix f = let {x = f x} in x
这看起来是不是很...神奇？你可能想知道：fix f 难道不会导致 f 无限嵌套应用的无限序列吗？比如：x = f x = f (f x) = f (f (f ( ... )))？这里问题的解决方案是惰性求值。本质上，如果（且仅当）f 是一个惰性函数，那么这个无限的 f 应用序列将被避免。让我们看一些例子。
例子： fix 的例子
Prelude> :m Control.Monad.Fix Prelude Control.Monad.Fix> fix (2+) -- Example 1 *** Exception: stack overflow Prelude Control.Monad.Fix> fix (const "hello") -- Example 2 "hello" Prelude Control.Monad.Fix> fix (1:) -- Example 3 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...
我们首先导入 Control.Monad.Fix 模块，将 fix （也被 Data.Function 模块导出）引入作用域。然后，我们尝试三个例子。让我们试着看看第一个例子中实际发生了什么。
-- fix f = let {x = f x} in x
fix (2+)
= let {x = 2 + x} in x
= let {x = 2 + x} in 2 + x
= let {x = 2 + x} in 2 + (2 + x)
= let {x = 2 + x} in 2 + (2 + (2 + x))
= let {x = 2 + x} in 2 + (2 + (2 + (2 + x)))
= ...
第一个例子使用 (+)，这是一个 急切 函数；它需要知道 x 的值才能计算...x 的值。因此，这个计算永远不会停止。现在让我们看看第二个例子。
fix (const "hello")
= let {x = const "hello" x} in x
= let {x = const "hello" x} in const "hello" x
= let {x = const "hello" x} in "hello"
= "hello"
这非常不同：我们注意到，在 fix 展开一次之后，求值很快就会终止，因为 const 忽略了它的第二个参数。最后一个例子的求值有点不同，但我们可以用类似的方法进行。
fix (1:)
= let {x = 1 : x} in x
= let {x = 1 : x} in 1 : x
这里 1 : x 已经处于 弱首范式 中（(:) 是一个惰性数据构造函数），因此展开停止。这实际上创建了一个循环结构。每次消费者函数请求此列表的新元素时，都会查询 x 的定义，并且它已经被知道是 1 : x。
因此，按顺序请求此列表中的元素将不断返回 1，没有限制。所以 take 10 (fix (1:)) 将产生一个包含十个 1 的列表，但是尝试通过在 GHCi 中键入 fix (1:) 来打印它们，会导致无限的 1 流被打印出来。
实际上，它会导致 show (fix (1:)) = "[" ++ intercalate "," (map show (fix (1:))) ++ "]" 的求值，虽然 map show (fix (1:)) 永远不会完全完成它的工作，但它确实会增量地、逐块地、每次一个 "1" 地生成输出。
"[" ++ intercalate "," (map show (fix (1:))) ++ "]"
= "[" ++ intercalate "," (map show (let {x = 1 : x} in x)) ++ "]"
= "[" ++ intercalate "," (map show (let {x = 1 : x} in 1 : x)) ++ "]"
= "[" ++ "1" ++ "," ++ intercalate "," (map show (let {x = 1 : x} in x)) ++ "]"
= "[1," ++ intercalate "," (map show (let {x = 1 : x} in 1 : x)) ++ "]"
= "[1," ++ "1" ++ "," ++ intercalate "," (map show (let {x = 1 : x} in x)) ++ "]"
= "[1,1," ++ intercalate "," (map show (let {x = 1 : x} in 1 : x)) ++ "]"
= "[1,1," ++ "1" ++ "," ++ intercalate "," (map show (let {x = 1 : x} in x)) ++ "]"
= "[1,1,1," ++ intercalate "," (map show (let {x = 1 : x} in 1 : x)) ++ "]"
= ...
这就是惰性求值的工作方式：打印函数不需要在开始打印之前消耗整个输入字符串，它只要可以就立即开始打印。
最后，迭代地计算一个数字的平方根的近似值：
-- fix f = let {x = f x} in x
fix (\next guess tol val -> if abs(guess^2-val) < tol then guess else
next ((guess + val / guess) / 2.0) tol val)
2.0 0.0001 25.0
= (let {rec = (\next guess tol val -> if abs(guess^2-val) < tol then guess else
next ((guess + val / guess) / 2.0) tol val) rec}
in rec) 2.0 0.0001 25.0
= let {rec guess tol val = if abs(guess^2-val) < tol then guess else
rec ((guess + val / guess) / 2.0) tol val}
in rec 2.0 0.0001 25.0
= 5.000000000016778
| 练习 |
|---|
|
以下表达式会收敛到什么值（如果有的话）？
|
fix 也可以用一种不引入结构共享的方式定义：
fix :: (a -> a) -> a
fix f = -- x where {x = f x}
-- f x where {x = fix f}
f (fix f)
函数 f 的不动点 是一个值 a，使得 f a == a。例如，0 是函数 (* 3) 的不动点，因为 0 * 3 == 0。这就是 fix 名字的由来：它找到函数的最小定义的不动点。（我们很快就会解释“最小定义”的含义。）对于上面提到的两个收敛的例子，这一点很容易看出。
const "hello" "hello" = "hello" (1:) [1,1,..] = [1,1,...]
由于不存在这样的数字 x，使得 2+x == x，所以 fix (2+) 发散也很合理。
| 练习 |
|---|
对于上面练习中你认为 fix f 收敛的每个函数 f，请验证 fix f 是否找到了一个不动点。 |
事实上，从 fix 的定义来看，它找到一个不动点是显而易见的。我们只需要将 fix 的方程反过来写：
f (fix f) = fix f
这正是不动点的定义！因此，似乎 fix 应该总是找到一个不动点。但是，有时 fix 似乎失败了，因为它有时会发散。然而，如果我们引入一些 语义学，我们可以修复这个属性。每个 Haskell 类型实际上都包含一个名为底的特殊值，记为 ⊥。因此，例如，类型为 Int 的值实际上包括 ⊥ 以及 1, 2, 3 等。发散的计算用 ⊥ 表示，也就是说，我们有 fix (2+) = ⊥。
特殊值 undefined 也用 ⊥ 表示。现在我们可以理解 fix 如何找到像 (2+) 这样的函数的不动点。
例子： (2+) 的不动点
Prelude> (2+) undefined *** Exception: Prelude.undefined
因此，将 undefined （即 ⊥）输入到 (2+) 会得到 undefined。所以 ⊥ 是 (2+) 的不动点！
在 (2+) 的情况下，它是唯一的不动点。然而，还有一些其他函数 f 具有多个不动点，而 fix f 仍然发散：fix (*3) 发散，但我们在上面提到过 0 是该函数的不动点。这就是“最小定义”条款发挥作用的地方。Haskell 中的类型有一个叫做定义度的偏序关系。在任何类型中，⊥ 都是最小定义的值（因此被称为“底”）。对于像 Int 这样的简单类型，偏序关系中唯一的对是 ⊥ ≤ 1、⊥ ≤ 2 等等。对于任何非底的 Int，我们都没有 m ≤ n。类似的评论适用于其他简单类型，例如 Bool 和 ()。对于像列表或 Maybe 这样的“分层”值，情况更加复杂，我们将参考关于语义学 的章节。
因此，由于 ⊥ 是所有类型的最小定义的值，而 fix 找到最小定义的不动点，如果 f ⊥ = ⊥，那么我们就有 fix f = ⊥（反之亦然）。如果你已经阅读了语义学文章，你会认出这是一个严格函数的标准：当且仅当 f 是严格函数时，fix f 发散。
如果你已经遇到过 fix 的例子，很可能是与 fix 和递归相关的例子。这是一个经典的例子：
例子： 用 fix 编码递归
Prelude> let fact n = if n == 0 then 1 else n * fact (n-1) in fact 5 120 Prelude> fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5 120
这里我们使用 fix 来“编码”阶乘函数：注意（如果我们将 fix 视为语言原语），我们对 fact 的第二个定义完全不涉及递归。在像类型化的 lambda 演算这样的没有递归特性的语言中，我们可以引入 fix 来用这种方式编写递归函数。这里还有一些其他例子。
例子： 更多的 fix 例子
Prelude> fix (\rec f l -> if null l then [] else f (head l) : rec f (tail l)) (+1) [1..3] [2,3,4] Prelude> map (fix (\rec n -> if n == 1 || n == 2 then 1 else rec (n-1) + rec (n-2))) [1..10] [1,1,2,3,5,8,13,21,34,55]
那么，这是如何运作的呢？让我们首先从语义学的角度来解释我们的 fact 函数。为了简洁，我们定义：
fact' rec n = if n == 0 then 1 else n * rec (n-1)
这与上面第一个示例中的函数相同，只是我们给匿名函数命名，以便现在计算的是 fix fact' 5。fix 将找到 fact' 的不动点，即满足 f == fact' f 的函数 f。但让我们来扩展一下这到底意味着什么。
f = fact' f = \n -> if n == 0 then 1 else n * f (n-1)
我们所做的只是在 fact' 的定义中用 f 替换 rec。但这看起来完全像阶乘函数的递归定义！fix fact' 将自身作为第一个参数传递给 fact'，从而从高阶函数（在旧的 LISP 语法中也称为函数式）中创建一个递归函数，该函数表达了整个递归计算的一步。
我们也可以从更操作的角度来考虑问题。让我们实际扩展 fix fact' 的定义。
fix fact'
= fact' (fix fact')
= (\rec n -> if n == 0 then 1 else n * rec (n-1)) (fix fact')
= \n -> if n == 0 then 1 else n * fix fact' (n-1)
= \n -> if n == 0 then 1 else n * fact' (fix fact') (n-1)
= \n -> if n == 0 then 1
else n * (\rec n' -> if n' == 0 then 1 else n' * rec (n'-1)) (fix fact') (n-1)
= \n -> if n == 0 then 1
else n * (if n-1 == 0 then 1 else (n-1) * fix fact' (n-2))
= \n -> if n == 0 then 1
else n * (if n-1 == 0 then 1
else (n-1) * (if n-2 == 0 then 1
else (n-2) * fix fact' (n-3)))
= ...
请注意，使用 fix 使我们能够不断“展开” fact' 的定义：每次遇到 else 子句时，我们都会通过评估规则 fix fact' = fact' (fix fact') 生成 fact' 的另一个副本，该规则充当递归链中的下一个调用。最终我们会遇到 then 子句，并从该链中退出。
而且，通过将 fix 的共享定义放在本页顶部，fix fact' 将创建一个实际的递归函数，该函数使用自身来进行递归调用，而不是使用其副本。
fix fact'
= let rec = fact' rec in rec
= let rec = (\rec' n -> if n == 0 then 1 else n * rec' (n-1)) rec in rec
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in rec
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in
\n -> if n == 0 then 1 else n * rec (n-1)
= let rec = (\n -> if n == 0 then 1 else n * rec (n-1)) in
\n -> if n == 0 then 1
else n * (if n-1 == 0 then 1 else (n-1) * rec (n-2))
= ...
这得益于 Haskell 的 let 允许递归定义，实际上与 Scheme 的 letrec 在这方面类似。非共享 fix 定义不使用此方法，并且也适用于非递归 let - 虽然它本身也是递归定义的（此处），但它创建的函数实际上不是自引用的，并且通过重新创建自己的副本并调用它来实现递归，正如我们上面所见。这就是为什么在非递归语言中添加递归的一种方法是将 fix 添加到其中，作为一种基本构造。
fix 的非递归定义也存在。其中最简单、最著名的被称为Y 组合子。在非类型化 Haskell 中，它可以写成 y = u . (. u)，其中 u x = x x 被称为U 组合子。
| 练习 |
|---|
|
类型化 lambda 演算
[edit | edit source]在本节中，我们将扩展上一节中多次提到的一个观点：fix 如何使我们能够在类型化 lambda 演算中编码递归。它假定你已经了解类型化 lambda 演算。回想一下，在 lambda 演算中，没有 let 子句或顶级绑定。每个程序都是 lambda 抽象、应用和字面量的简单树。假设我们想写一个 fact 函数。假设我们有一个名为 Nat 的类型来表示自然数，我们会从以下类似的内容开始
λn:Nat. if iszero n then 1 else n * <blank> (n-1)
问题是，我们如何填写 <blank>？我们没有函数的名称，因此无法递归调用它。绑定名称到项的唯一方法是使用 lambda 抽象，所以让我们试一试
(λf:Nat→Nat. λn:Nat. if iszero n then 1 else n * f (n-1)) (λm:Nat. if iszero m then 1 else m * <blank> (m-1))
这扩展为
λn:Nat. if iszero n then 1
else n * (if iszero n-1 then 1 else (n-1) * <blank> (n-2))
我们仍然有 <blank>。我们可以尝试再添加一层
(λf:Nat→Nat. λn:Nat. if iszero n then 1 else n * f (n-1)
((λg:Nat→Nat. λm:Nat. if iszero m then 1 else m * g (m-1))
(λp:Nat. if iszero p then 1 else p * <blank> (p-1))))
->
λn:Nat. if iszero n then 1
else n * (if iszero n-1 then 1
else (n-1) * (if iszero n-2 then 1 else (n-2) * <blank> (n-3)))
很明显，无论我们添加多少层命名，我们都无法消除这个 <blank>。除非我们使用 fix，它本质上提供了一个对象，我们可以从中始终展开一层递归，并且仍然得到我们开始时的内容。
fix (λf:Nat→Nat. λn:Nat. if iszero n then 1 else n * f (n-1))
这是类型化 lambda 演算加上 fix 中一个完美的阶乘函数。
在类型化 lambda 演算的上下文中，fix 实际上比这更有意思：如果我们将其引入语言中，那么每种类型都将被填充，因为给定某个具体类型 T，以下表达式具有类型 T
fix (λx:T. x)
这在 Haskell 语言中就是 fix id，它在语义上是 ⊥。因此，我们看到，一旦我们将 fix 引入类型化 lambda 演算中，每个类型良好的项都减少到一个值的属性就会丢失。
Fix 作为数据类型
[edit | edit source]在 Haskell 中也可以创建 fix 数据类型。
有三种定义方法。
newtype Fix f = Fix (f (Fix f))
或者使用 RankNTypes 扩展
newtype Mu f = Mu (forall a . (f a -> a) -> a) data Nu f = forall a . Nu a (a -> f a)
Mu 和 Nu 有助于泛化折叠、展开和重新折叠。
fold :: (f a -> a) -> Mu f -> a fold g (Mu f) = f g unfold :: (a -> f a) -> a -> Nu f unfold f x = Nu x f refold :: (a -> f a) -> (g a -> a) -> Mu f -> Nu g refold f g = unfold g . fold f
Mu 和 Nu 是 Fix 的受限版本。Mu 用于创建归纳的非无限数据，而 Nu 用于创建共归纳的无限数据。例如）
newtype Stream a = Stream (Nu ((,) a)) -- exists b . (b, b -> (a, b)) newtype Void a = Void (Mu ((,) a)) -- forall b . ((a, b) -> b) -> b
与不动点函数不同，不动点类型不会导致底部。在以下代码中，Bot 被完美地定义。它等效于单元类型 ()。
newtype Id a = Id a newtype Bot = Bot (Fix Id) -- equals newtype Bot=Bot Bot -- There is only one allowable term. Bot $ Bot $ Bot $ Bot ..,
Fix 数据类型不能模拟所有形式的递归。例如，这种非正则数据类型。
data Node a = Two a a | Three a a a data FingerTree a = U a | Up (FingerTree (Node a))
使用 Fix 实现它并不容易。