What are some compelling use cases of infinite data structures?

Question

Some languages (Haskell, Clojure, Scheme, etc.) have lazy evaluation. One of the "selling points" of lazy evaluation is infinite data structures. What is so great about that? What are some examples of cases where being able to deal with infinite data structures is clearly advantageous?

Answer 1

Here are two examples, one big and one small:

Why Functional Programming Matters by John Hughes has a good example, of a chess game. The move tree for a chess game is not actually infinite, but its big enough that it might as well be infinite (call it "near-infinite"). In a strict language you can't actually treat it as a tree, because there isn't enough room to store the whole tree. But in a lazy language you just define the tree and then define a "nextMove" function to traverse it as far as necessary. The lazy evaluation mechanism takes care of the details.

The small example is simply associating an index number with every item in a list, so that ["foo", "bar", "baz"] becomes [(1,"foo"), (2,"bar"), (3,"baz")]. In a strict language you need a loop that keeps track of the last index and checks to see if you are at the end. In Haskell you just say:

zip [1..] items 

The first argument to zip is an infinite list. You don't need to work out how long it needs to be ahead of time.

Answer 2

A few advantages I can think of:

• Cleaner code - it is interesting to note that code to generate infinite sequences if often simpler and cleaner than code that operates on bounded data. This is because such code is often closer to the underlying mathematical definition.
• Flexibility - rather than decide ahead of time how large your data needs to be, if you write it using a lazy infinite structure you simply don't need to worry. It will "just work"
• Performance - if you use laziness correctly, you can use it to improve performance by only calculating data values as and when they are needed - and potentially not at all. So you can potentially avoid a large amount of unnecessary computation.
• Abstraction of infinite processes - there is an interesting use of infinite lazy sequences as an abstraction for streams of events, for example reading input from a network connection over time. This can create some very elegant and interesting ways of creating code to handle streams of events. e.g. see the stream-utils library in Clojure.
• Better algorithms - there are some algorithms that are more easily expressible with infinite data structures - the idea is that you lazily "pull in" the parts of the solution that you need while leaving the rest of the infinite algorithm unevaluated.If using this approach enables you to reduce the time complexity of your algorithm (say from O(n^2) to O(n log n)) then this can be a big win.