Infinite lists in Haskell

It is possible for us to define infinite lists in Haskell due to its lazy evaluation ⁶.

For example, the following defines an infinite list of 1-s:

a = 1 : a

The infinite list a definition says that it starts with a 1 to which a itself is added. ie, a is 1 followed by a itself.

(Fun fact: The a = 1 : a is same as a = (:) 1 a)

The first time I saw an infinite list like this, I was mighty puzzled being quite unfamiliar with Haskell.

What does the definition of a say?

It's a recursive definition.

But how can we add a list to itself when it has not yet been completely defined? How is the initial value of a found out? Only after having a value can we append it to the 1, right? Well, it needn't be so.

This is possible due to Haskell being a lazily evaluated language.

Unlike in the case of eager evaluation, the RHS of a's definition is not evaluated when the definition is bound to the variable a. ¹

The evaluation happens only when it is needed.

The infinite list a can be expanded like

a = 1 : a
  = 1 : (1 : a)
  = 1 : (1 : (1 : a))
  = ....
  = ....

But Haskell expands the definition only as much as it needs to.

Suppose we do something like take 2 a, then expansion proceeds but only till the required 2 elements are obtained.

take 2 a
take 2 (1 : a)
take 2 (1 : (1 : a))
-- expansion done

References

(This post is a modified form of something that I had scribbled down in 06 September 2021 based on what heard in the class teaching us Haskell. ⁷)