[Haskell-cafe] How to use infinite lists to define the list of all negative integers

[Andrew Wagner]

Hi Bahtijar!

I'm not going to answer your question directly, but let me give you
some background that will hopefully help you discover the pretty
solution yourself.

Consider this definition:
ones = 1 : ones     -- This list is essentially [1,1,1,...]

And this expression:
take 5 ones

Now, suppose for some reason we need to evaluate this expression to
find its value. It would seem that this evaluation would take an
infinite amount of time. But because Haskell only evaluates what's
necessary, it does something like this:
take 5 ones
take 5 (1 : ones)
take 5 (1 : (1 : ones))
take 5 (1 : (1 : (1 : ones)))
take 5 (1 : (1 : (1 : (1 : ones))))
take 5 (1 : (1 : (1 : (1 : (1 : ones)))))
[1,1,1,1,1]

So, it only looks at the first five elements of the infinite list,
because that's all it needs. Now let's take a slightly harder (but
more classical) example:

fibs = 0:1:zipWith (+) fibs (tail fibs)

zipWith (+) just takes the first element of each of two lists and adds
them together. (tail fibs) gives fibs, but without the first element.
So, it will add the first element to the second element, the second to
the third (which was calculated as needed by adding the first two),
and so on.

So, one way to define an infinite list of negative numbers is to say
"the first negative number is -1, and the rest of the list is what you
get if you subtract -1 from every number in the list".  Then, the
second number will be the first number in the "rest of the list", so
it will be the number you get by subtracting -1 from the first number
in the list. The third number will be the first of the rest of the
rest of the list (say that ten times fast), and will be the first
number of the list you get by adding -1 to the list starting at the
second number. Etc., etc.

One final note: Max's solution also works, but this is a good way to
practice working with infinite lists, lazy evaluation, and list
functions. Don't miss the opportunity! Please feel free to email me or
the list with any questions.

Andrew
On 2/5/07, Bahtijar Vogel <bahtijarvogel at gmail.com> wrote:
> Hi,
> How am I supposed to use infinite lists to define the list of all negative
> integers?
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
>