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

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]。

然而，当我尝试xs在 GHCi 中进行评估时，我得到了

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

但它不会停止计算。

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

Answer 1

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

\n

也就是说[1,2,3,4,2,4,4] ++ undefined，哪个更小。它更小，因为它比第一个定义更少。

\n

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

\n

这是总体前景。但具体来说，我们可以一步一步地进行计算，命名所有中间值并扩展定义，我们会发现结果上的“get”点赶上了最初更靠前的“put”点，但是“获取”点比“放置”点快两倍。因此，当他们相遇时，我们还没有放置任何我们可以得到的东西。

\n

因此，计算陷入困境，等待有东西出现在什么都没有的地方，并且没有任何东西可以把任何东西放在那里。

\n

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

\n

在一个不相关的注释中，我会调用该函数seconds，而不是second。

\n\n

所以事情是这样的：

\n

xs = [1,2,3,4] ++ second xs\n\n              a b c         (_:a:p) = xs = [1,2,3,4]++second xs\n              \xe2\x86\x93 \xe2\x86\x93 \xe2\x86\x93         (_:b:q) = p  = [    3,4,2]++second p\n   =  1 2 3 4 2 4 4         (_:c:r) = q  = [        2,4]++second q\n        \xe2\x86\x93   \xe2\x86\x93   \xe2\x86\x93   \xe2\x86\x93                 r  = [            4]++second r\n        a   b   c    \n      \xe2\x86\x91   \xe2\x86\x91   \xe2\x86\x91   \xe2\x86\x91                  r = drop 2 q = second q = \n      xs  p   q   r                    = second (2:4:r) = 4:second r\n

\n

head r是明确定义的，它是

\n

r = drop 2 q = second q \n             = second (_:c:r) \n             = c:second r\nhead r = c = 4\ntail r = \n

\n

但接下来我们需要找到tail r. 是(:)数据节点吗？是吗[]？

\n

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

\n

因此，要找出second r( (1)) 是什么，我们需要找出( ) 是什么second r(2)。

\n

我们被困住了。

\n