Anyone else have an opinion? Bertram Felgenhauer pointed out to me that a friendlier-looking expression is intersperse x xs = drop 1 $ fromList xs <**> fromList [const x, id] but this still may not be the most obvious thing. The main question, I think, is whether anyone is likely to *use* an intersperse function for sequences. If so, I think we should add it; if not, probably not. On Mon, Dec 22, 2014 at 7:11 AM, Felipe Lessa wrote:

On 22-12-2014 09:03, David Feuer wrote:

...

containers master now uses a new mechanism to implement <*> that can also be used directly to implement an efficient intersperse function corresponding to the one in Data.List. The real question is whether anyone wants one. The potential for clashing names is obviously a point against. The other is that the same asymptotic bounds (but almost certainly worse constant factors) can be obtained using

intersperse x xs = drop 1 $ forwards $ Backwards (fromList [const x, id]) <*> Backwards xs

If the name clash is the only downside, I'm +1. That intersperse definition isn't obvious :).

Cheers,

-- Felipe.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

I'm with Greg on this one. Due to Sequence being abstract I think it's even more crucial to have a rich API. I think little missing things like intersperse move me back to using lists frequently. On Sat, Dec 27, 2014 at 10:04 AM, Greg Weber wrote:

Sequence is not used nearly enough. I think anything useful in the List API should also be in the Sequence API. On Sat, Dec 27, 2014 at 5:50 AM, David Feuer wrote:

...

Anyone else have an opinion? Bertram Felgenhauer pointed out to me that a friendlier-looking expression is

intersperse x xs = drop 1 $ fromList xs <**> fromList [const x, id]

but this still may not be the most obvious thing. The main question, I think, is whether anyone is likely to *use* an intersperse function for sequences. If so, I think we should add it; if not, probably not.

On Mon, Dec 22, 2014 at 7:11 AM, Felipe Lessa wrote:

...

On 22-12-2014 09:03, David Feuer wrote:

...

containers master now uses a new mechanism to implement <*> that can also be used directly to implement an efficient intersperse function corresponding to the one in Data.List. The real question is whether anyone wants one. The potential for clashing names is obviously a point against. The other is that the same asymptotic bounds (but almost certainly worse constant factors) can be obtained using

intersperse x xs = drop 1 $ forwards $ Backwards (fromList [const x, id]) <*> Backwards xs

If the name clash is the only downside, I'm +1. That intersperse definition isn't obvious :).

Cheers,

-- Felipe.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

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 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

It depends what you mean. Seq has nice asymptotics but quite poor constant factors. Do you consider DList as requiring a separate building phase? If so, the answer is quite possibly that the data structure you want doesn't exist. But for most code I think the existing solutions are good enough (and performance requirements lax enough) that nobody has put much effort into anything better. John L. On 08:30, Sun, Dec 28, 2014 Greg Weber 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 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

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

clojure-style persistent vectors based on hashed array mapped tries, or RRB-trees [1][2] would be great to have. the basic structure is the same for unordered-container's hash maps, so reusing code there is a possibility. b 1 - http://infoscience.epfl.ch/record/169879/files/RMTrees.pdf 2 - https://github.com/clojure/core.rrb-vector/

On Dec 29, 2014, at 8:09 AM, Ross Paterson wrote:

On Sun, Dec 28, 2014 at 11:01:46AM +0200, Roman Cheplyaka 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).

Clearly Seq uses more space than arrays, but I estimate that a large Seq uses between 5/6 and 4/3 of the space of an equivalent list, with Seq's built with deque operations tending toward the lower end and append/split moving them toward the middle of the range. So I'd say they're about the same (unless the list is deforested, of course). Do you have measurements that give different results?

...

It probably has its use cases, but most of the time you'd be better off with one of the other choices:

Those choices will beat Seq on particular operation mixes, but the virtue of Seq is that it gives decent performance over a broad set of operations. _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries

On Dec 29, 2014 11:09 AM, "Ross Paterson" wrote:

Those choices will beat Seq on particular operation mixes, but the virtue of Seq is that it gives decent performance over a broad set of operations.

One of the nice things about that is that you can use Seq when you're still figuring out just what your program will be doing with its sequences and get a pretty good idea of the general performance characteristics. If Seq turns out to be a constant-factor performance bottleneck, you can replace it with something more specialized later, once you know *exactly* what operations you need.