为什么这个定点计算不停止？

Question

我是 Haskell 的新手，我有以下代码：

second (x:y:xs) = y : second xs  -- returns every second element of a list
second _ = []

xs = [1,2,3,4] ++ second xs

我希望 xs 的计算结果为 [1,2,3,4,2,4,4]，因为那是不动点，即 [1,2,3,4,2,4,4] == [1,2,3,4] ++ second [1,2,3,4,2,4,4].

但是，当我尝试在 GHCi 中计算 xs 时，我得到

Prelude> xs
[1,2,3,4,2,4,4

但它不会停止计算。

谁能解释为什么这不会停止，有没有一种简单的方法可以让计算停止并且 return [1,2,3,4,2,4,4]?

Answer 1

[1,2,3,4,2,4,4] ++ []是([1,2,3,4] ++) . second的a不动点，但不是最小的不动点。

即[1,2,3,4,2,4,4] ++ undefined，即小。它更小，因为它比第一个更不明确。

第一个更明确，因为它定义了第 7 个尾巴，而第二个的第 7 个尾巴是 undefined。

这是总体看法。但是具体我们可以一步一步的计算，命名所有的中间值并扩展定义，我们会发现结果上的“get”点赶上了最初更靠前的“put”点，但是“get”点比“put”快两倍。所以当他们见面时，我们还没有放在那里我们可以得到的东西。

因此计算卡住了，等待什么东西出现在什么都没有的地方，也没有什么东西可以放在那里。

避免这种情况的唯一方法是将 take 7 放在它上面。

在一个不相关的注释中，我将该函数称为 seconds，而不是 second。

所以它是这样的：

xs = [1,2,3,4] ++ second xs

              a b c         (_:a:p) = xs = [1,2,3,4]++second xs
              ↓ ↓ ↓         (_:b:q) = p  = [    3,4,2]++second p
   =  1 2 3 4 2 4 4         (_:c:r) = q  = [        2,4]++second q
        ↓   ↓   ↓   ↓                 r  = [            4]++second r
        a   b   c    
      ↑   ↑   ↑   ↑                  r = drop 2 q = second q = 
      xs  p   q   r                    = second (2:4:r) = 4:second r

head r定义好，就是

r = drop 2 q = second q 
             = second (_:c:r) 
             = c:second r
head r = c = 4
tail r =

但是我们需要找到 tail r。它是一个 (:) 数据节点吗？是[]吗？

       = tail (c:second r)
       = second r               -- (1)
       = second (c:second r)
       = case (c:second r) of
           (x:y:z) -> y:second z
           []      -> []
       = case (second r) of     -- (2)
           (y:z) -> y:second z

所以要找出 second r ( (1) ) 是什么，我们需要找出 什么 second r ( (2) ) 是.

我们卡住了。

Answer 2

另一种更直观的查看方式是 []（列表末尾）必须来自某个地方。 second 函数只会 return [] 一旦它在输入中遇到 [] ，所以你最终会遇到先有鸡还是先有蛋的情况。在这种情况下，[] 永远不会产生，因此计算永远不会停止。

为什么这个定点计算不停止？

Why doesn't this fixed-point computation stop?

haskell

infinite-loop

lazy-evaluation

infinite-recursion

fixpoint-combinators