如何评估 `fix f = let {x = f x} in x`？

Question

如何评估 `fix f = let {x = f x} in x`？

haskelllazy-evaluationevaluationfixpoint-combinators

9

fix f = let {x = f x} in x

谈到 let，我认为 let P = Q in R 将首先求出 Q -> Q'，然后用 Q' 替换 R 中的 P，即: R[P -> Q']。

但是在 fix 定义中，Q 取决于 R，那么如何进行求值呢？

我想这与惰性求值有关。Q' 变成了一个 thunk，但我无法在脑海中推导出这一点。

作为背景，我在研究 Y 组合子，它应该能够找到函数的不动点，因此如果我有这个函数，one x = 1，那么 fix one == 1 必须成立，对吗？

因此，fix one = let {x = one x} in x，但我不明白 1 是如何从中产生的。

- geckos

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- chi · Accepted Answer

谈到let，我认为let P = Q in R 会评估Q -> Q'然后用Q'替换P在R中，或者说：R [P -> Q']。

道义上是这样，但是P不会立即被评估，它会在需要时才进行评估。

但是在fix定义中，Q依赖于R，如何进行评估？

Q不依赖于R，而是依赖于P。这使得P递归地依赖于自己。这可能会导致几种不同的结果。简单地说：

如果Q在评估P之前无法返回其任何部分，则P表示无限递归计算，不会终止。例如，

let x = x + 1 in x     -- loops forever with no result
-- (GHC is able to catch this specific case and raise an exception instead,
-- but it's an irrelevant detail)

如果Q在需要评估P之前可以返回其结果的一部分，则会这样做。

let x = 2 : x in x
-- x = 2 : .... can be generated immediately
-- This results in the infinite list 2:2:2:2:2:.....

let x = (32, 10 + fst x) in x
-- x = (32, ...) can be generated immediately
-- hence x = (32, 10 + fst (32, ...)) = (32, 10+32) = (32, 42)

我想这是关于惰性求值的。 Q' 变成了一个 thunk，但我无法在脑海中推导出它的原理。

P 与一个 thunk 关联。重要的是这个 thunk 在返回输出的一部分之前是否调用自己。

作为背景，我正在研究 Y combinator，它应该找到函数的不动点，所以如果我有这个函数 one x = 1，那么 fix one == 1 必须成立，对吗？

没错。

所以 fix one = let x = one x in x，但我看不出为什么 1 会从中产生。

我们可以这样计算：

fix one
 = {- definition of fix -}
let x = one x in x
 = {- definition of x -}
let x = one x in one x
 = {- definition of one -}
let x = one x in 1
 = {- x is now irrelevant -}
1

只需扩展定义。保留递归定义以备将来需要。