I don't quite understand how seq exactly works and how to implement a function using seq. So as an exercise, if I want to implement a function that generates a list starting with a number a.
for example, I'm using the following function
countup n = n : countup (n+1)
and trying to get [1, 2, 3, 4 ...] (starting from 1, just increment 1 and add to the list) as an infinite lazy list. How should I do this?
UPDATED:
I'm trying to make (take k (countup 0)) to use O(1) space. Here, take function is as follows:
take k (x:xl) =
if k==0
then x
else take (k-1) xl
countup n = n : countup (n+1)
Each element of the list is created as a thunk previousElement + 1. So if you take the 1000000th or whatever element, that will be a very large thunk (...(n + 1)... + 1) containing ~1000000 suspensions. Even though the :-cells can be GC'd as soon as they are made (so traversing the list spine itself takes O(1) space), the elements themselves duplicate the structure of the list and so take k (countup n) still takes O(k) space.
We would like it if evaluating the : cells would also evaluate the elements. We can do that with
countup n = seq n $ n : countup (n + 1)
Now, when evaluating seq n $ n : countup (n + 1), seq will cause both n and n : countup (n + 1) to be evaluated. Evaluating the latter does nothing (it is already evaluated), and evaluating the former performs any thunked addition so that the + 1s never build up. With this definition, take k (countup n) takes O(1) space (or, really O(log(n + k))).
We can also write the improved function as
countup !n = n : countup (n + 1)