What is the most efficient purely functional algorithm for generating all prefixes of a list?

Question

prefixes ls = zipWith take [1 .. length ls] (repeat ls)

Is there any way to do better than this? Intuitively, it seems to me that one can't get an algorithm below O(n²) in a purely functional language because either reverse or append must be applied n times. I have no idea how to prove this, though.

Answer 1

I think you are right. There can be no sharing of the spine of the list because all the tails are different. Therefore the list of prefixes, if fully evaluated, would take the full Θ(n²) space, which must take Ω(n²) time to generate.

Note that (a lazier version of) the function you wrote is available in Data.List as inits.

There is a neat optimization you can do though. This equation holds:

map (foldl f z) . inits = scanl f z

And scanl runs in linear time. So if you can phrase the thing you want to do to each prefix as a left fold, then you can avoid the quadratic complexity of building the list of prefixes.

Answer 2

Isn't that representation-dependent? If you represent lists as contiguous storage plus start and end index (similar to bytestrings), you can share the storage and just need to traverse once to build the list of indices. The algorithm would not change, just the representation. For this particular use case, using snoc lists (binary lists, but nested from the end, not the start, of the list) would also allow for sharing of sublists, right?