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.

Answer 3

There is the canonical pure memoization strategy:

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

We map the fib' function over an infinite list to construct a table of all the values of fib. Voila! Cheap, easy memoization.

Of course, this has lookup time linear in the argument. You can replace it with an infinite trie to get logarithmic lookup time. cf. data-inttrie.

Answer 4

I was going to comment regarding @knivil's Scheme. Instead I'll just throw this up as another answer.

Lazy data structures aren't the only way to accomplish most tasks. This might irritate Pythonistas. But I believe it's best when programmers get to choose which techniques they use. Lazy techinques are powerful and elegant.

Knivil mentioned using Scheme's iota. Look how easy it is to write the full method (with all 3 args), relying on laziness:

iota count begin step = let xs = begin:map (+step) xs
                        in take count xs

-- or, alternately
iota count begin step = take count $ map ((+begin).(*step)) [0..]

I could also write length for non-empty lists by abusing laziness:

len = fst . last . zip [1..]

-- or even handling empty lists
len = fst . last . zip [0..] . (undefined:)

Consider the powerful and elegant iterate function defined in Prelude.

iterate f x = x : iterate f (f x)

It creates the infinite list [x, f x, f (f x), f (f (f x)), ...]. I could have written iota in terms of iterate:

iota count begin step = take count $ iterate (+step) begin

The lazy approach is an elegant way to program. It's not the only way, and people used to C or Java will certainly cry out "but I don't need laziness, I can just _", and they are correct. If your language is Turing-complete, it can be done. But laziness can be oh so elegant.

Answer 5

Well, I had a nice use case for that last month. I needed a generator for unique names when copying objects. That means, the generator takes the original name X, and generates a new name for the copy. It does that by appending a text like

X - copy
X - copy (2)
X - copy (3)
...

as long as the name is not used within the set of objects within the same group. Using an "infinite data structure" (an infinite array of strings) for that instead of a simple loop has one advantage: you can separate the name generating part completely from the test if the name is already in use. So I could reuse the generator function for different types of objects where the in-use test is slightly different for each object type.

Answer 6

Infinite data structures provide elegant representations of (computable) real numbers. For example, an infinite list like

[(0, 4), (1, 3.5), (3.1, 3.2), ...]

can represent pi. WIth built in laziness, operating on this representation becomes easy.