这个函数（haskell）是怎么回事？

Question

我有这个haskell函数，我不太明白。

ns :: [Integer] 
ns = 0 : [n+k | (n, k) <- zip ns [1,3..]] 

我被要求“需要3纳秒”。

我以为ns是不变的，所以它只会压缩列表的第一个元素，给（0,1）。然后，当添加给出答案1.然后它说“取3纳秒”，所以我压缩0与列表的前5个元素，给出...（0,1），（0,3），（0,5 ），然后添加时，我得到[1,3,5]的最终答案。但这不是正确的答案。

ns实际发生了什么？我很努力去理解...

Answer 1

haskell是懒惰，所以你可以有递归定义。这里是它的布局。

ns = 0 : something 

(n,k) <- zip (0 : something) [1,3,5,7...] 
(n,k) <- [(0,1) : something) 

ns = 0 : 1 : something 

(n,k) <- zip (0 : 1 : something) [3,5,7...] 
(n,k) <- (0,1) : (1,3) : something 

ns = 0 : 1 : 4 : something 

(n,k) <- zip (0 : 1 : 4 : something) [5,7...] 
(n,k) <- (0,1) : (1,3) : (4,5) : something 

ns = 0 : 1 : 4 : 9 : something 

.... 

看看我们如何确定下一个元组是什么，然后添加它的两个元素。这使我们能够确定下一个元素。

Answer 2

Haskell中的所有内容都是懒惰的，因此虽然ns是恒定的，但这并不意味着列表中的项目不能在以后“添加”（或更准确地说，“计算”）。另外，因为ns是递归定义的，所以稍后出现在列表中的值可能取决于列表中较早出现的值。

让我们一步一步地回顾一下。

首先，我们知道，ns从0开始，所以暂时，ns看起来是这样的：

ns: 0, ?, ?, ... 

那么什么是在第一个问号？根据您的功能，这是n + k，其中n是ns中的第一个元素，并且k是[1, 3..]中的第一个元素。所以n = 0,k = 1和n + k = 1。

ns: 0, 1, ?, ... 

移动上，下元件也n + k，在这里我们使用的ns和[1, 3...]第二元件。我们现在知道ns的第二个元素是1，所以n = 1,k = 3和n + k = 4。

ns: 0, 1, 4, ... 

依此类推。

Answer 3

Haskell懒洋洋地评估事物，所以它只会精确计算所需的值。这意味着我们需要以某种方式需要ns的值来了解它是如何计算的。

head ns 
head (0 : ...) 
0 

显然，head不会强制够什么有趣的事情发生，但你已经可以看到，ns有趣的部分是刚刚被丢弃。当我们要求更多的时候，这种效果会更进一步，比如打印每个元素。让我们逐个强制每个元素来查看模式。首先，让我们来取代列表解析与一个相当的函数调用

zipWith f []  _  = [] 
zipWith f _  []  = [] 
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys 

ns = 0 : zipwith (+) ns [1,3..] 

现在，我们可以通过一个评估ns一个元素。真的，要更详细一点，我们正在评估ns并确定第一个构造函数是(:)，然后决定将第二个参数作为我们的下一步计算为(:)。我将使用{...}表示尚未评估的thunk。

ns 
{ 0 } : zipWith (+) ns [1,3...] 
{ 0 } : zipWith (+) ({ 0 } : { ... }) [1,3...] -- notice the { 0 } thunk gets evaluated 
0  : { 0 + 1 } : zipWith f { ... } [3,5...] 
0  : 1   : { 1 + 3 } : zipWith f { ... } [5,7...] 
0  : 1   : 4   : { 4 + 5 } : zipWith f { ... } [7,9...] 

什么是重要的上述需要注意的是，由于ns得到评估只能一块一块的，它从来没有要求知道的东西还没有被计算。这样，ns本身就形成了一个紧密，巧妙的小循环。

Answer 4

ns :: [Integer] 
ns = 0 : [n+k | (n, k) <- zip ns [1,3..]] 

这是一个核心数据定义。 ns是一个常量，一个列表，但由于Haskell是懒惰的，因此它被访问“充实”。

一个例证：

1  n1 n2 n3 n4 n5 ... -- the list ns, [n1,n2,n3,...], 
2  0 1 4 ...   -- starts with 0 
3  ----------------- 
4  1 3 5 7 9  -- [1,3..] 
5  ----------------- 
6  1 4 ...   -- sum the lines 2 and 4 pairwise, from left to right, and 
7  n2 n3 n4 n5 ...  -- store the results starting at (tail ns), i.e. from n2 

---

我们可以看到，正是如何访问迫使列表ns进入存在有步骤，例如print $ take 4 ns后，通过命名临时实体：

ns :: [Integer] 
ns = 0 : [n+k | (n, k) <- zip ns [1,3..]] 

ns = 0 : tail1 
tail1 = [n+k | (n, k) <- zip ns [1,3..]] 
     = [n+k | (n, k) <- zip (0 : tail1) [1,3..]] 
     = [n+k | (n, k) <- (0,1) : zip tail1 [3,5..]] 
     = 1 : [n+k | (n, k) <- zip tail1 [3,5..]] 
     = 1 : tail2 

tail2 = [n+k | (n, k) <- zip (1 : tail2) [3,5..]] 
     = [n+k | (n, k) <- (1,3) : zip tail2 [5,7..]] 
     = 4 : tail3 

tail3 = [n+k | (n, k) <- zip (4 : tail3) [5,7..]] 
     = 9 : tail4 

tail4 = [n+k | (n, k) <- zip (9 : tail4) [7,9..]] 
------  
ns = 0 : 1 : 4 : 9 : tail4 

Answer 5

这相当于ns = 0 : (zipWith (+) ns [1,3,...])，这可能是更容易理解：第k + 1元件是第k个元素加上第k个奇数，与合适的起始条件。