Joachim Breitner's Homepage

Two years ago, I discussed various ways of constructing a list in a Monad (or, more specifically, in IO) in Haskell, and compared their merits in terms of elegance, stack usage, number of traversals of the list and run-time efficiency.

Recently, two blog posts discussed the issue further and proposed new, more daring alternatives. Neil Mitchell breaks through the abstraction provided by IO, duplicates “the world” and traverses the list twice, and obtains a speed-up for long lists.

Twarn van Laarhoven went even further and wrote custom C– code to destructively update the tail-pointer of the list cell to be able to create the list completely evaluated on the first start. This basically answers my question from two years ago:

I’m still wondering: What would be required from Haskell, GHC or the monads in question to have a fully satisfactory solution here, i.e. one that is as fast as the naive recursion, as stack efficient as the difference list solution, and allocates no thunks, only list cells?

He also has a variant with a slightly nicer interface around “holes”, i.e. explicit objects on the heap that can later be replaced by indirections. Obviously, both approaches are very unsafe.

I took this as an opportunity to redo my benchmark measurements, and include their variants (named escapeIO, hackIO and holeIO). The following table omits the variants with quadratic performance, as I ran it on longer lists now:

The following graph shows that around 10000, the naive approaches become much slower and the fancy hacks pay of, with Twarn’s tail-pointer-updating code performing the best:

I would really like to see a package that provides a API like Twarn’s holes, either in this raw unsafe variant (but with the garbage collector related code checked), or with a safe API using type hackery similar to the ST monad that ensures that after “normal” code gets its hands on a term possibly involving holes, the holes may no longer be modified.

I have put the code and results on GitHub.