Infinite List

In Haskell, we can define infinite lists recursively, as shown below:

ones = 1:ones

You can see that ones is defined as 1 prepended to ones. In typical imperative languages, this would be unacceptable syntax if ones is not previously defined as a list. However, it is completely fine in Haskell because Haskell is lazily evaluated. We can perform operations on infinite lists like the following:

head ones -- 1
take 5 ones -- [1,1,1,1,1]
take 5 (map (*2) ones) -- [2,2,2,2,2]

However, not all functions for lists are applicable to infinite lists. For example, the following operations are problematic:

tail ones -- Infinitely runs (DONT DO THIS!)
count ones -- Err

We can see that functions requiring the evaluation of the entire list result in errors.

Usages

When would we use infinite lists? We can use them for defining infinite lists corresponding to sequences like natural numbers, even numbers, odd numbers, prime numbers, and so on:

-- Natural Numbers
nat = asc 1
  where asc n = n : (asc $ n + 1)
 
-- Even Numbers
even = map (*2) nat
 
-- Odd Numbers
odd = filter (\x -> mod x 2 == 0) nat

We can create an infinite sequence of numbers with more complex rules, such as the Fibonacci sequence:

f 0 = 0
f 1 = 1
f n = (f $ n - 1) + (f $ n - 2)
 
fibs = map f nat

However, we have to be careful about how we define infinite lists. The above definition for Fibonacci is not ideal as it has to compute every number's Fibonacci sequence up until n for every n, which has O(2^n) time complexity (really bad). The below is how it should be defined instead:

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

What is going on in the above definition? The zipWith function applies an operator (in this case, +) to two lists to combine them into one list. As we sum each element of fibs and tail fibs (which lacks the first element 0 from fibs), we can effectively continue summing up the two previous numbers and create an infinite list of the Fibonacci sequence. This is a better implementation because we keep track of the previous two numbers to compute the next.

Exercises

This is an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #19 - Infinite Lists. YouTube.