16:30 I think there is sharing going on, in the very definition of ones = 1:ones. ones is a fully realized infinite list, a single cons cell referring to itself and therefore repeating forever. This is different from e.g. [1..], which is an infinite list of unique cons cells, impossible to realize whole in memory.
I'm a bit confused about the sieve of eratosthenes implementation, and I'm assuming my confusion comes from my lack of understanding of the order in which ghc lazily evaluates this function. - start the list comprehension for 2 - run into 3, which is not a multiple of 2 - at this point what happens? 3 passes the list comp condition, and so does the compiler start to evaluate the sieve for 3? but then when it runs into 4, which isn't a multiple of 3 (but is a multiple of 2), what happens here? does my confusion make sense?
I believe it's this: (i) sieve [2..] (ii) sieve (2 : [3..]) (iii) 2 : sieve [x | x ← [3..], mod x 2 ≠ 0] (iv) 2 : sieve (3 : [x | x ← [4..], mod x 2 ≠ 0]) (v) 2 : 3 : sieve [y | y ← [x | x ← [4..], mod x 2 /= 0], mod y 3 ≠ 0]] (vi) 2 : 3 : sieve [y | y ← (5 : [x | x ← [6..], mod x 2 /= 0]), mod y 3 ≠ 0]] (vii) 2 : 3 : sieve (5 : [y | y ← [x | x ← [6..], mod x 2 /= 0], mod y 3 ≠ 0]] (viii) 2 : 3 : 5 : sieve [z | z ← [y | y ← [x | x ← [6..], mod x 2 /= 0], mod y 3 ≠ 0]], mod z 5 ≠ 0] I am writing the variables as x, y, z instead of x, x, x only because it is unreadable enough already. (i) → (ii) for pattern matching (ii) → (iii) because of outermost evaluation (iii) → (iv) for pattern matching (iv) → (v) because of outermost evaluation (v) → (vii) for pattern matching, which involves (v) → (vi) because of outermost evaluation? In any case, the xs list needs to be evaluated once for any y to be generated. (vi) → (vii) is again outermost evaluation? List comprehensions are hard to categorise for me. I suppose one could compute the xs list further, but ys is outside so that is evaluated first. (vii) → (viii) because of outermost evaluation. Note that the pattern matching steps are still outermost evaluation, since "sieve ..." can't be expanded before doing that. *How* the compiler is able to achieve this insane nested evaluation order is far above my pay grade, but this is what lazy + outermost suggests.
16:30 I think there is sharing going on, in the very definition of ones = 1:ones. ones is a fully realized infinite list, a single cons cell referring to itself and therefore repeating forever. This is different from e.g. [1..], which is an infinite list of unique cons cells, impossible to realize whole in memory.
This is what I thought too. I expected Graham to draw pointers there.
I'm a bit confused about the sieve of eratosthenes implementation, and I'm assuming my confusion comes from my lack of understanding of the order in which ghc lazily evaluates this function.
- start the list comprehension for 2
- run into 3, which is not a multiple of 2
- at this point what happens? 3 passes the list comp condition, and so does the compiler start to evaluate the sieve for 3? but then when it runs into 4, which isn't a multiple of 3 (but is a multiple of 2), what happens here?
does my confusion make sense?
I believe it's this:
(i) sieve [2..]
(ii) sieve (2 : [3..])
(iii) 2 : sieve [x | x ← [3..], mod x 2 ≠ 0]
(iv) 2 : sieve (3 : [x | x ← [4..], mod x 2 ≠ 0])
(v) 2 : 3 : sieve [y | y ← [x | x ← [4..], mod x 2 /= 0], mod y 3 ≠ 0]]
(vi) 2 : 3 : sieve [y | y ← (5 : [x | x ← [6..], mod x 2 /= 0]), mod y 3 ≠ 0]]
(vii) 2 : 3 : sieve (5 : [y | y ← [x | x ← [6..], mod x 2 /= 0], mod y 3 ≠ 0]]
(viii) 2 : 3 : 5 : sieve [z | z ← [y | y ← [x | x ← [6..], mod x 2 /= 0], mod y 3 ≠ 0]], mod z 5 ≠ 0]
I am writing the variables as x, y, z instead of x, x, x only because it is unreadable enough already.
(i) → (ii) for pattern matching
(ii) → (iii) because of outermost evaluation
(iii) → (iv) for pattern matching
(iv) → (v) because of outermost evaluation
(v) → (vii) for pattern matching, which involves
(v) → (vi) because of outermost evaluation? In any case, the xs list needs to be evaluated once for any y to be generated.
(vi) → (vii) is again outermost evaluation? List comprehensions are hard to categorise for me. I suppose one could compute the xs list further, but ys is outside so that is evaluated first.
(vii) → (viii) because of outermost evaluation.
Note that the pattern matching steps are still outermost evaluation, since "sieve ..." can't be expanded before doing that.
*How* the compiler is able to achieve this insane nested evaluation order is far above my pay grade, but this is what lazy + outermost suggests.