Haskell uses a lazy evaluation system which allows you define as many terms as you like, safe in the knowledge that the compiler will only allocate the ones you use in an expression. In this article we use simple sequences as lists of infinite length in a number of different ways to demonstrate how you can use this approach.
Programming with infinite lists open up a new way of writing programs, where you give rules for generating a sequence rather than building it by hand — often leading to simpler code. Since data types are lazy and support self references, you can produce a list dynamically by defining it as a function of its successors.
The simplest example of this is the sequence of natural numbers (ie. [1,2,3,4,..]) — there are a few different ways of doing this in Haskell:
numbers1 = 1 : map (+1) numbers1 numbers2 = 1 : [x+1 | x <- numbers2] numbers3 = [1..] $ ghci *Main> take 10 numbers1 [1,2,3,4,5,6,7,8,9,10] *Main> take 10 numbers2 [1,2,3,4,5,6,7,8,9,10] *Main> take 10 numbers3 [1,2,3,4,5,6,7,8,9,10]
Obviously, the third method here is the simplest, it’s the standard shorthand for linear sequences and acts like the range function in other languages. You can use it to generate linearly increasing or decreasing sequences concisely:
*Main> [1..10] [1,2,3,4,5,6,7,8,9,10] *Main> [1,3..10] [1,3,5,7,9] *Main> [10..1] [] *Main> [10,9..1] [10,9,8,7,6,5,4,3,2,1] *Main> take 20 [10,9..] [10,9,8,7,6,5,4,3,2,1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9]
When we look at the lists numbers1 and numbers2, the important thing is that each refers to itself in order to build the list. Even though the list is never complete, we can build each item in the list by using the sequence’s latest value at that point in the program. This works equally well with functions that produce lists, such as map, as with list comprehensions. The items in the list are built only when they are needed, generating previous items if necessary, so even though the sequence is potentially limitless, it wont take up an infinite amount of memory.
A more complicated example is generating the sequence of factorial numbers and triangular numbers. The following example code demonstrates both self referential list comprehension implementations, and those based on the built in scanl function (for the list comprehension examples, you’ll need to give ghci the -fglasgow-exts command line option):
triangle1 = scanl (+) 1 [2..] triangle2 = 1 : [x+y | x <- [2..] | y <- triangle2] factorial1 = scanl (*) 1 [2..] factorial2 = 1 : [x*y | x <- [2..] | y <- factorial2] $ ghci -flglasgow-exts *Main> (take 1000 triangle1) == (take 1000 triangle2) True *Main> (take 1000 factorial1) == (take 1000 factorial2) True *Main> take 10 triangle1 [1,3,6,10,15,21,28,36,45,55] *Main> take 10 factorial2 [1,2,6,24,120,720,5040,40320,362880,3628800]
Another common example when demonstrating infinite lists is the Fibonacci sequence — Wikipedia’s page on Haskell gives two ways of implementing this sequence as an infinite list — I’ll add another using scanl.
fibs1 = 0 : 1 : zipWith (+) fibs1 (tail fibs1) fibs2 = 0 : 1 : [ a+b | a <- fibs2 | b <- tail fibs2 ] fibs3 = 0 : scanl (+) 1 fibs3 $ ghci -fglasgow-exts *Main> (take 1000 fibs1) == (take 1000 fibs2) True *Main> (take 1000 fibs2) == (take 1000 fibs3) True *Main> take 10 fibs3 [0,1,1,2,3,5,8,13,21,34]
The uses of infinite lists are not limited to integer sequences — for example the following function uses an infinite list to generate all possible strings less than a given number of characters:
strings = [x++[a] | x <- "" : strings, a <- ['a'..'z']] stringsLessThan n = takeWhile (\x -> length x < 5) strings $ ghci *Main> length (stringsLessThan 3) 702
They’re not useful in all situations, but they give you another tool you can use to make your code simpler and more concise. Basic profiling has indicated that for a basic task an iterative program and a list based program perform equivalently, that is there’s no penalty in utilising laziness in your code.
If you want to read more about using lazy lists in Haskell, the Haskell Wiki is your best bet, in particular this page on building an infinite list of prime numbers is a good example of where the technique can be used.
