[Haskell-cafe] Re: FASTER primes

[Daniel Fischer]

Am Freitag 08 Januar 2010 18:37:21 schrieb Will Ness:
> Daniel Fischer <daniel.is.fischer <at> web.de> writes:
> > Am Donnerstag 07 Januar 2010 11:43:44 schrieb Heinrich Apfelmus:
> > > Will Ness wrote:
> > >
> > > Hm? In my world view, there is only reduction to normal form and I
> > > don't see how "allocate its own storage" fits in there. Okasaki
> > > having shown something to that end would be new to me?
> >
> > Perhaps what was meant was "storage must be allocated for each filter"
> > (which, however, seems trivial).
>
> I still contend that in case of nested filters, where each filter has
> only one consumer, even that isn't ultimately necessary (a chain of
> pointers could be formed). That's because there's no "peek"s, only
> "pull"s there. If the filters are used in merge situation, then there
> will be some "peek"s so current value must be somehow stored, though
> it's better to be made explicit and thus static (the place for it, I
> mean, instead of the "rolling" cons cell). Such implementation technique
> would prevent some extra gc.
>

Well, for each filter we need to store

1. a pointer to where in the wheel we are
2. the prime by which to multiply the steps of the wheel
3. the current value of the filter (which number to reject next)

I don't see how to use less. It's not much, but it's not zero storage.