On Thu, Nov 20, 2014 at 11:00 AM, Ross Paterson <R.Paterson@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.