> On Jun 22, 2016, at 5:41 PM, Dave Abrahams via swift-evolution > <[email protected]> wrote: > >> I agree, names are not the primary issue. >> >> Another issue is that you cannot currently write generic code that >> might need to iterate a sequence more than once. You currently have >> to over-constrain types to `Collection` even if you don’t need to do >> anything other than iterate the elements (the discussion about whether >> `LazyFilterSequnce` has a bug in its `underestimateCount` is relevant >> here). > > That's not an over-constraint. Multi-pass-ness *is* the fundamental > distinction between Sequence and Collection. AFAIK there's no multipass > sequence that cannot support indices.
Just wanted to communicate more around this point specifically. If Collections
can be infinite (probably adding special meaning to count returning
Collection.IndexDistance.max), then the only difference between Sequence and
Collection is the indexes.
However, I’m concerned about the delta between an iterator and a full
collection. For an example:
class FibIterator : IteratorProtocol {
var last = 0, current = 1
func next() -> Int? {
(last, current) = (current, current + last)
return current
}
}
If subscript indexing on collections isn't required to be an O(1) operation, I
don’t see a reason for Sequence to exist - we can simply enumerate the sequence
with a numeric index, and iterate up to that count to resolve. But this makes
things surprising for those implementing generic algorithms across Collections.
I don’t see a way to get an O(1) integer index and meet all the efficiency
constraints of Collection without either memoization or additional complexity
on implementing FibIterator.
1. we could use integer indexes and use a non-recursive technique for
calculating the fibonacci value at the specified index. FibIterator basically
is rewritten into a function “fibonacci(at index:Int)”.
2. We could use a copy of FibIterator as the index, since it is a value type.
FibIterator would need to implement Comparable.
2a. We make the index InfiniteSequenceIndex< FibIterator >, where the
wrapper is there to define a consistent EndIndex value.
However, Collection’s index(_:offsetBy) allows for negative offsets,
which would not be accomplished in O(n).
2b. If FibIterator gains an extra method to become bidirectional we can
support index(_:offsetBy) in O(n) time. Note that you would probably want to
have a bidirectional iterator define its own endIndex.
-DW
signature.asc
Description: Message signed with OpenPGP using GPGMail
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
