Fastest immutable list data structure for lots of concatenation and a single iteration

Question

I'm working with Haskell. Standard list concatenation is naive and slow. My situation is I have an algorithm that builds up a single list concatenating (order doesn't matter, so it could be either prepend or append or a combination) many times, and then returns it. The result will then be used only once. High performance is critical.

So, it's a pretty simple situation. I heard about difference lists and that it helps with this situation. But is that the best option?

The lists could grow to be large: 100,000's of entries.

Answer 1

This is an empirical question and should be answered empirically. Reasonable alternatives include

• Standard list with cons (called "prepend" in your question)

• Difference list (John Hughes list) with constant-time append

• Algebraic data type supporting constant-time append:

  data Alist a = ANil | ASingle a | AAppend (Alist a) (Alist a)
  

• List of lists with final concat.

All these will take linear time. But constant factors matter, and the only way to find out is to build and measure. If you want you can create a microbenchmark that is completely faithful to your original code, but performs only list operations, by logging every list operation into a writer monad. But that is probably a huge pain in the ass and just not worth it. Instead, write a simple benchmark, compile (with optimization turned on), and measure.

And please let us know the results.