*Problem:*
.prefix() works eagerly even on LazyCollectionType. This means access is
not O(1).
*Implications:*
There's no way to only get the first N elements of a lazy sequence without
a nasty for loop. If prefix() used on a lazy sequence, it'll trigger
computation on the whole array, just to return the first N elements.
*Proposal:*
It would be more more useful if lazy.<insert methods here>.prefix() returned
LazyPrefixCollection<Generator.Element>
instead of
Slice<LazyCustomCollection<Range<Generator.Element>>>.
That way prefix() could be used to chain *pure lazy operations*, like
lazy.filter().map().filter().prefix().map() which can be quite useful in
some cases.
I understand that this has implications, and it would make prefix() less
consistent in terms of return type.
But, this pattern seem to be used in this context already - it wouldn't be
a much different than how how lazy.filter() is implemented, since it also
returns a custom LazySequenceType instead of SequenceType.
Has this been considered before? Would there be any cases where this would
create unintended side effects?
As far as I see, it wouldn't change the meaning and behaviour of prefix(),
only would it extend its usefulness.
I think this would be a good addition for forward and bidirectional
collections. You'd need two separate implementations for forward and
bidirectional wrappers.
For random-access collections, the eager implementation is optimal
(finding the end index runs in O(1) and Slice<> does not introduce any
constant factor compared to non-trivial wrappers), and we should keep
that behavior by adding an overload that would return a
LazyCollection<Slice<Base>>.
Dmitri
···
On Sun, Feb 14, 2016 at 2:51 AM, Mark Aron Szulyovszky via swift-evolution <swift-evolution@swift.org> wrote:
Problem:
.prefix() works eagerly even on LazyCollectionType. This means access is not
O(1).
Implications:
There's no way to only get the first N elements of a lazy sequence without a
nasty for loop. If prefix() used on a lazy sequence, it'll trigger
computation on the whole array, just to return the first N elements.
Proposal:
It would be more more useful if lazy.<insert methods here>.prefix() returned
LazyPrefixCollection<Generator.Element>
instead of
Slice<LazyCustomCollection<Range<Generator.Element>>>.
I think you can continue with writing a formal proposal in the
swift-evolution repository, presenting the full API that you are
proposing.
Dmitri
···
On Sun, Feb 14, 2016 at 4:12 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Sun, Feb 14, 2016 at 2:51 AM, Mark Aron Szulyovszky via > swift-evolution <swift-evolution@swift.org> wrote:
Problem:
.prefix() works eagerly even on LazyCollectionType. This means access is not
O(1).
Implications:
There's no way to only get the first N elements of a lazy sequence without a
nasty for loop. If prefix() used on a lazy sequence, it'll trigger
computation on the whole array, just to return the first N elements.
Proposal:
It would be more more useful if lazy.<insert methods here>.prefix() returned
LazyPrefixCollection<Generator.Element>
instead of
Slice<LazyCustomCollection<Range<Generator.Element>>>.
Thanks, Mark!
I think this would be a good addition for forward and bidirectional
collections. You'd need two separate implementations for forward and
bidirectional wrappers.
For random-access collections, the eager implementation is optimal
(finding the end index runs in O(1) and Slice<> does not introduce any
constant factor compared to non-trivial wrappers), and we should keep
that behavior by adding an overload that would return a
LazyCollection<Slice<Base>>.
Cool, thanks, it's in the making! Sorry I was really busy this week.
Can you tell me why is it required to have different implementation for
Forward and Bidirectional LazyCollectionTypes?
Otherwise it's all clear!
Thanks a lot!
Cheers,
Mark
···
On Mon, 22 Feb 2016 at 02:55 Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Sun, Feb 14, 2016 at 4:12 AM, Dmitri Gribenko <gribozavr@gmail.com> > wrote:
> On Sun, Feb 14, 2016 at 2:51 AM, Mark Aron Szulyovszky via > > swift-evolution <swift-evolution@swift.org> wrote:
>> Problem:
>> .prefix() works eagerly even on LazyCollectionType. This means access
is not
>> O(1).
>>
>> Implications:
>> There's no way to only get the first N elements of a lazy sequence
without a
>> nasty for loop. If prefix() used on a lazy sequence, it'll trigger
>> computation on the whole array, just to return the first N elements.
>>
>> Proposal:
>> It would be more more useful if lazy.<insert methods here>.prefix()
returned
>> LazyPrefixCollection<Generator.Element>
>> instead of
>> Slice<LazyCustomCollection<Range<Generator.Element>>>.
>
> Thanks, Mark!
>
> I think this would be a good addition for forward and bidirectional
> collections. You'd need two separate implementations for forward and
> bidirectional wrappers.
>
> For random-access collections, the eager implementation is optimal
> (finding the end index runs in O(1) and Slice<> does not introduce any
> constant factor compared to non-trivial wrappers), and we should keep
> that behavior by adding an overload that would return a
> LazyCollection<Slice<Base>>.
Hi Mark,
I think you can continue with writing a formal proposal in the
swift-evolution repository, presenting the full API that you are
proposing.
The reason to have different implementations is so that a result of
applying prefix() to a bidirectional collection is also a
bidirectional collection. If we had just one lazy wrapper, the result
of prefix() would always be a forward collection. You might also need
to do the same for random access, I haven't thought it through well
enough to say if it would certainly be needed. But we want
xs.lazy.prefix() to preserve the collection category (forward,
bidirectional, random access) in the result.
Creating multiple types wouldn't be needed if we had a generics
feature that we don't have now -- conditional protocol conformances.
We want that, and will eventually have it, but for now, we have to go
with multiple types.
Dmitri
···
On Sun, Feb 28, 2016 at 5:36 AM, Mark Aron Szulyovszky <mark.szulyovszky@gmail.com> wrote:
Hi Dmitri,
Cool, thanks, it's in the making! Sorry I was really busy this week.
Can you tell me why is it required to have different implementation for
Forward and Bidirectional LazyCollectionTypes?