Functional Streams

A pretty standard functional data type is the Stream. It behaves similarly to a list (in that it has a head and a tail), however with a stream the ‘rest’ of the list is lazily generated on demand. This allows one to create a data structure that can represent an infinite sequence without the storage requirements (helpful if you only need the first few values).

This is similar to what we have in the base class libraries with IEnumerator. Using that interface one can easily implement an infinite sequence. However, IEnumerator interface is destructive. That is, once you call MoveNext the underlying state is invariably affected and you are left with different enumerator than we had before. This means that you can’t share the iterator with anyone and you are forced to create a new one every time. This, of course, makes it quite difficult to do things lazily. You could spent 15 minutes lazily evaulating one sequence, and the next person to get that sequence will have to recompute all those values as well. Allowing lazily evaluated streams into our library allows for sharing space and for sharing the time necessary to evaluate.

With the functional streams you can can move down the stream without affecting state. So i can be looking at any section of it without any issues. Another nice thing is that it’s trivially easy to get a subsequence of the stream, or to append two streams together. This is much easier to do now in C# with the addition of iterators to the language, however, you still get destructive iterators in the process.

Comments (4)

  1. The Streams in OCaml where really cool when writing parsers 😉

    Is there a generics-enabled interface for streams coming up in C# 2.0?

  2. Dave Thomas says:

    The re-opening of closed streams would be a usefill addition, I have a problem when I was caching xsd files in a hash table and passing them to the XmlUrlResolver, it kindly closed the underlying stream for me. I had to end up caching the byte arrays, any ideas on this?

  3. Julien: Agreed. So beautiful in it’s simplicity.