>> * Given just an `Index`, you need to be able to calculate the next `Index`,
>> and check if it lies before the `endIndex`. The complexity of this is hidden
>> in your example because you're relying on a traditional `DictionaryIndex` to
>> perform these tasks. Thus, the `Index` type in your dictionary design would
>> be some sort of wrapper-around-the-key, not the key itself. That's the
>> source of the `subscript(_: Index) -> Value` which apparently confused you.
>
> This was an implementation detail, see the comment at the top of the file. If
> SE0065 is implemented then the previous/next/lastIndex can be found from the
> collection in constant amortized time. This is possible after SE0065.
>
> I wasn't confused, but I was unsure of the best approach. Array and
> Dictionary probably need different Indexable-style protocols.
I suspect that's a non-starter.
The Collection protocol encapsulates this semantic:
1. The type is a Sequence of finite length which always (unless it's
mutated) contains the same elements in the same order.
2. The Index represents a location in the Sequence.
3. Indexing with an Index retrieves the element at that location.
4. You can retrieve the successor index to a given index; sub-protocols
provide other ways to transform indices.
5. You can == one Index with another, and if they match, they refer to
the same element.
6. With SE-0065, you can also < one Index with another to see which one
comes earlier in the collection.
Both Array and Dictionary (as well as other types like Set and String (or
rather, String's views)) need to support these semantics. Array and String are
ordered collections—any element can appear at any index—so the Index is the
main means by which we access the collection's elements. Set and Dictionary are
not ordered, so we have other ways to access their elements. This difference is
Also note that SE-0065 makes this harder, not easier. Requirement #6—that Index
must be Comparable—would require Dictionary keys to be Comparable and
Dictionary iteration to happen in sorted order. Since the natural order of
Dictionary key access is (roughly) by hashValue, this would make iterating over
the Dictionary very slow, or would require a separate, sorted storage for the
keys, or something along those lines.
The alternative to that is to disconnect Index from Key. If you do that, then
Index is basically just the index of the element in the linear storage backing
the Dictionary, and iteration is almost as fast as looping over an Array—you
just have to skip over unused buckets. That's a much saner way to handle
things. So this:
> I also think that, ideally, `Index == Key` for a Dictionary.
Turns out to be incorrect. Iterating over a Dictionary by Key is not a
particularly good solution.
Alternatively, you might think of it this way: what you describe here:
> There may be an index-like type which allows lookup with a lower constant
> overhead (bucket index), but it's likely to only be used by extensions, if at
> all.
*is* what Collection is for.
> I'm fine for `Array(newDictionary)` to discard keys, there's always
> `Array(newDictionary.enumerate())`. I think it's more consistent for filter
> to work on values. I think all collections would also benefit from versions
> of map/filter/reduce etc. that also have an Index (so you could get every
> second value of an array, for example).
As I mentioned (and brought up on another thread for discussion), that's not
what `enumerate()` is for.
> I'd like the protocol to have associatedtype FilterType, for NewDictionary it
> would be defined as something like:
> typealias FilterType = NewDictionary<Key,Value>
> This would allow filter, reduce, etc. to preserve the keys.
>
> * Your `map` is overloading `SequenceType.map` merely by return type. That
> means you can no longer assign it directly to a newly-declared variable, or
> use it in many other contexts where the type has to be inferred.
>
> Overloading is an implementation detail at the moment, as mentioned in the
> comment at the top of the file. Ideally this would be Self.MapType once we
> have generic associatedtypes. For dictionaries:
> typealias MapType<T> = NewDictionary<Key,T>
The use of "typealias" here is misleading, because these aren't really
typealiases—they're associated types. Generic associated types are not
currently a feature of Swift. I'm not sure if they're even in the generics
manifesto.
> Either way I think all collections would benefit from a property that exposes
> a sequence of (Index,Value) pairs.
Agreed.
>> * The keys are disposable and the values are the important part—most
>> operations on a Dictionary would throw away the keys and use only the values.
>
> Agreed, this may add complexity to generic/default implementations, or
> require changes to some of the protocols (my preference is protocol changes).
I'm not necessarily saying that a Value-oriented Dictionary is wrong, but I'm
not sure it's right, either.
>> * Index still would not be a Key—it would be some kind of instance which
>> wrapped or converted into a Key.
>
> After SE0065 they can be the same.
They can't; see above.
--
Brent Royal-Gordon
Architechies
_______________________________________________
swift-evolution mailing list
[email protected]
https://lists.swift.org/mailman/listinfo/swift-evolution
