[Haskell-cafe] Improving *> and >> for Data.Sequence

[David Feuer]

To be precise, I *think* using the fromList approach for <*> makes us
create O(n) thunks in order to extract the last element of the result. If
we build the result inward, I *think* we can avoid this, getting the last
element of the result in O(1) time and space. But my understanding of this
data structure remains primitive.

On Fri, Nov 21, 2014 at 12:17 PM, David Feuer <david.feuer at gmail.com> wrote:

> On Thu, Nov 20, 2014 at 11:00 AM, Ross Paterson <R.Paterson at city.ac.uk>
> wrote:
>
>> On Thu, Nov 20, 2014 at 12:37:49AM +0000, Ross Paterson wrote:
>> > On Wed, Nov 19, 2014 at 02:58:46PM -0500, David Feuer wrote:
>> > > I got to looking at <*> just now, and it suggests the
>> > > following question: is there a particularly efficient way to build a
>> Seq when
>> > > its ultimate size is known in advance, avoiding the usual incremental
>> > > rebuilding?
>> >
>> > The following avoids the rebuilding, but I haven't tweaked or timed it:
>> >
>> > [...]
>>
>> Actually this is pretty much what the existing fromList2 does.
>>
>
> I think the technique fromList2 uses is probably sub-optimal for <*>,
> because it steps through things in order. The ends of fs <*> xs don't
> depend on the middle of f. It should be better, I think, to delay actually
> touching that middle until it's actually demanded.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141121/76a5e5a5/attachment.html>