Functions are essentially infinite pairs of input and output, so why not have data with infinite components?

Some examples

The infinitely long list of spaces:

white :: String
-- Remember a string is a list of characters
white = ' ' : white

The infinitely long list of natural numbers:

nats :: [Int]
-- Note there's no base case, because the list isn't empty or anything.
-- Interesting use of map here.
nats = 0 : map (+1) nats
-- Or more concisely:
nats = [0..]

Or from the practicals, the infinitely long list of Pascal’s triangle rows (using iterate):

ptriangle = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]

This opens up some new possibilities. For example you can define the fibonacci sequence efficiently using an infinite list.

Processing message streams

Somehow, functions computing over infinite lists can also be viewed as processes communicating with their context by streams of messages. Bit confusing…Note this is conceptual concurrency. Not real concurrency. Best to look at the notes for this, as they have diagrams.

Tabulation

table :: (Int->a) -> [a]
table f = map f [0..]

This is like a ‘representation changer’. It creates an infinite list of the results of applying function ‘f’ to the list of natural numbers (an infinite list in itself). Thanks to lazy evaluation, this is fine, because it doesn’t try to evaluate f for every natural number.

You can use this to yet again implement the fibonacci sequence in another way. See notes for the code.