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

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]++ 秒 [1,2,3,4,2,4,4]。

但是，当我尝试在 GHCi 中评估 xs 时，我得到了

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]++) 。第二个，但它不是最小的固定点。

即[1,2,3,4,2,4,4]++ undefined，更小。它更小，因为它比第一个定义更少。

第一个定义更多，因为它的第 7 个尾部已定义，而第二个的第 7 个尾部是 undefined。

这就是总体前景。但具体来说，我们可以一步一步地计算，命名所有中间值并扩展定义，我们会发现结果上的“get”点 catch 了最初更靠前的“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) ) 是什么，我们需要找出 what second r ( (2) ) 是。

我们被困住了。