3

我是 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]？

4

2 回答 2

5

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

也就是[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)。

我们被困住了。

于 2021-10-02T17:41:40.287 回答
4

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

于 2021-10-02T17:53:54.743 回答