[swift-users] 2 x lazy collection bugs

[Dmitri Gribenko]

On Mon, Feb 8, 2016 at 8:56 PM, Howard Lovatt via swift-users
<swift-users at swift.org> wrote:
> Hi,
>
> I think I have found a couple of bugs in lazy collections; just checking
> before filling. The following code is a filter map version of the Sieve of
> Eratosthenes:
>
> func lazyFilterMapForEachLoop(limit: Int = 9) -> [Int] {
>
>     var possibles = Array(count: limit + 1, repeatedValue: true)
>
>     return (2 ... limit).lazy.filter { i in // Has to be lazy and sequential
> so that `possibles` is updated before it is used

Before looking at your questions below, I want to note that this is
not a supported way of using the lazy subsystem.  The issue is that
you seem to be relying on the evaluation order.  It is not guaranteed,
even if you can reliably reproduce a certain evaluation order in the
current version of the library.

> The filter closure is called twice per trial integer! First without
> preceding to the map stage at all, i.e. all values are filtered out! Second
> time through the numbers it does proceed to the map stage as you would
> expect.

Again, remember that you are using the *lazy* subsystem.  The
evaluation order of the closures you are passing to the operations is
not guaranteed.  Closures can be evaluated once, more than once, or
not at all, and in the order that the library choses.  Closures are
required to be pure, so you are not allowed to observe how many times
and in which order they were actually evaluated.

The reason why the closure is evaluated twice is because you end up
calling an eager map(), which tries to reserve the array capacity
suitable for the result.  To do that, map() calls 'count' on the lazy
filter collection, which triggers the computation the first time.

It is an open question though, whether calling the closure twice is
profitable here, and what can we do about it.  The idea though is that
those reallocations can sometimes be quite expensive when the closure
is cheap to execute.  OTOH, when the closure is expensive to evaluate,
calling it twice is a loss.

> It produces an "Index out of range" error despite the fact that maximum
> number processed is 9 which is an allowable index of `possibles`.

Are you sure you didn't mean to use ..< instead of ...?

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/