Sequence vs LazyList

Question

I can't wrap my head around the differences between sequence and LazyList. They're both lazy and potentially infinite. While seq<'T> is IEnumerable<'T> from .NET framework, LazyList is included in F# PowerPack. In practice, I encounter sequences much more often than LazyLists.

What are their differences in terms of performance, usage, readability, etc? What are reasons for such a bad reputation of LazyList compared to that of seq?

Answer 1

LazyList computes each element only once regardless of how many times the list is traversed. In this way, it's closer to a sequence returned from Seq.cache (rather than a typical sequence). But, other than caching, LazyList behaves exactly like a list: it uses a list structure under the hood and supports pattern matching. So you might say: use LazyList instead of seq when you need list semantics and caching (in addition to laziness).

Regarding both being infinite, seq's memory usage is constant while LazyList's is linear.

These docs may be worth a read.

Answer 2

In addition to Daniel's answer, I think the main practical difference is how you process the LazyList or seq structures (or computations).

• If you want to process LazyList, you would typically write a recursive function using pattern matching (quite similar to processing of normal F# lists)

• If you want to process seq, you can either use built-in functions or you have to write imperative code that calls GetEnumerator and then uses the returned enumerator in a loop (which may be written as a recursive function, but it will mutate the enumerator). You cannot use the usual head/tail style (using Seq.tail and Seq.head), because that is extremely inefficient - because seq does not keep the evaluated elements and the result of Seq.head needs to re-iterate from the start.

Regarding the reputation of seq and LazyList, I think that F# library design takes a pragmatic approach - since seq is actually .NET IEnumerable, it is quite convenient for .NET programming (and it is also nice because you can treat other collections as seq). Lazy lists are not as frequent and so normal F# list and seq are sufficient in most of the scenarios.