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

How `fix f = let {x = f x} in x` is evaluated?

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

谈到 let,我认为 let P = Q in R 会计算 Q -> Q' 然后 P 在 R 中被 Q' 替换,或者:R[P -> Q'].

但是在fix定义中Q依赖于R,那么如何求值呢?

我想这是关于惰性求值的。 Q' 变成了一个砰的一声,但我无法在脑海中推理出这个。

根据上下文,我正在查看 Y 组合器,它应该找到一个函数的不动点,所以如果我有这个函数,one x = 1 ,那么 fix one == 1 一定成立,对吧?

所以 fix one = let {x = one x} in x,但我看不出 1 会怎样。

Talking about let, I thought that let P = Q in R would evaluate Q -> Q' then P is replaced by Q' in R, or: R[P -> Q'].

从道德上讲,是的,但是 P 不会立即评估,而是在需要时评估。

But in fix definition the Q depends on R, how to evaluate then?

Q不依赖于R,而是依赖于P。这使得 P 递归地依赖于自身。这可能会导致几种不同的结果。粗略地说:

  • 如果 Q 在计算 P 之前不能 return 其结果的任何部分,那么 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 之前可以代替 return 其结果的一部分,它会这样做。

    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)
    

I imagine that this is about lazy evaluation. Q' becomes a thunk, but I can't reason this in my head.

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

As a matter of context, I'm looking at Y combinator, it should find a fixed point of a function so if I have this function. one x = 1, then fix one == 1 must hold, right?

是的。

So fix one = let x = one x in x, but I can't see why 1 would emerge from that

我们可以这样计算:

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

只需扩展定义即可。保留递归定义以备不时之需。