Does anyone want intersperse for Data.Sequence?

David Feuer david.feuer at
Sun Dec 28 16:39:21 UTC 2014

I'm not sure what you mean. Appending sequences is already efficient.
intercalate is approximately O(sum $ fmap (log . length) xs), which is much
better than what you'd get from lists. The peculiar nice thing about
intersperse that you don't get from intercalate is that you can index or
split in O(log(min{i,n-i})) time immediately. So if you have a 2^40-element
sequence, xs, then (intersperse 5 xs) `index` (2^39) will take on the order
of 39 operations. There is no way to accomplish this with intercalate using
2-3 finger trees, and I don't know of any data structure that would support
such a thing (I doubt it's possible).
On Dec 28, 2014 11:30 AM, "Greg Weber" <greg at> wrote:

> I want an interface that supports efficient appending without requiring a
> separate building phase or other hassles. Does this not exist?
> I get that a library author might want to deal with the hassle of
> alternatives. But as an application author there are times that all I care
> about is a clean and simple interface that supports efficient appends.
> On Sun, Dec 28, 2014 at 1:01 AM, Roman Cheplyaka <roma at> wrote:
>> On 27/12/14 17:03, Greg Weber wrote:
>> > Sequence is not used nearly enough.
>> Not really. Seq has high constant factors and for small sizes is often
>> slower than plain lists. Nor is it space-efficient (for big sizes).
>> It probably has its use cases, but most of the time you'd be better off
>> with one of the other choices:
>> * plain old lists
>> * difference lists (trees)
>> * lists "without remorse"
>> * vectors
>> * lazy vectors (lists of vectors)
>> Roman
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list