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 : aThe 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
(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. ⁷)