What is going on in this function (haskell)?

问题:

I have this haskell function that I don't quite understand.

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

I am asked to "take 3 ns".

I thought ns was constant so it would only zip with the first element of the list, giving (0,1). Then when added gives an answer of 1. Then it says "take 3 ns" so I zipped 0 with the first 5 elements of the list, giving... (0,1),(0,3), (0,5) and then when added, I get a final answer of [1,3,5]. However this isn't the correct answer.

What is actually happening to ns? I'm struggling to understand...

回答1:

haskell is lazy so you can have recursive definitions. Here it is laid out.

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

....

See how we determine what the next tuple is then add its two elements. This allows us to determine the next element.

回答2:

Everything in Haskell is lazy, so while ns is constant, that doesn't mean items in the list can't be "added" (or more accurately, "computed") at a later time. Also, because ns is recursively defined, values that appear later in the list can depend on values that appear earlier in the list.

Let's go over this step by step.

First, we know that ns starts with 0, so for the time being, ns looks like this:

ns: 0, ?, ?, ...

So what's in the first question mark? According to your function, it's n + k, where n is the first element in ns, and k is the first element in [1, 3..]. So n = 0, k = 1, and n + k = 1.

ns: 0, 1, ?, ...

Moving on, the next element is also n + k, where we use the second elements of ns and [1, 3...]. We now know that the second element of ns is 1, so n = 1, k = 3, and n + k = 4.

ns: 0, 1, 4, ...

And so on.

回答3:

Haskell evaluates things lazily, so it'll only compute exactly as much of a value is needed. That means we need to somehow need values of ns to see how it's computed.

 head ns
 head (0 : ...)
 0

Clearly, head doesn't force enough for anything interesting to happen, but you can already see that the interesting part of ns is just discarded. That effect goes further when we ask for more, such as printing each element. Let's just force each element one after another to see the pattern. First, let's replace the list comprehension with a single equivalent function call

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

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

Now we can evaluate elements of ns one by one. Really, to be more detailed, we're evaluating ns and determining that the first constructor is (:) and then deciding to evaluate the second argument to (:) as our next step. I'll use {...} to represent a not-yet-evaluated 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...]

What's important to note above is that since ns get evaluated only piece by piece, it never demands to know something that has not yet been computed. In this way, ns forms a tight, clever little loop all in itself.

回答4:

That's equivalent to ns = 0 : (zipWith (+) ns [1,3,...]) , which may be easier to comprehend: the k+1th element is the kth element plus k-th odd number, with appropriate starting conditions.

回答5:

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

this is a corecursive data definition. ns is a constant, a list, but it is "fleshed out" by access, since Haskell is lazy.

An illustration:

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

---

We can see precisely how access is forcing the list ns into existence step by step, e.g. after print $ take 4 ns, by naming the interim entities:

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