[swift-evolution] [Discussion] Dictionary Key as Index

[Andrew Bennett]

I've moved this discussion over from "[swift-evolution] [Proposal]
mapValues" which discusses mapValues, like map but it preserves keys and
transforms values, returning a Dictionary.

I'm in favour mapValues, but I feel like it should be the default behaviour
of map for a Dictionary. Being the default requires changes to protocols
(many already planned), language features (already planned), and addressing
many interface inconsistencies between Array and Dictionary.

---- continuing from the other thread ----

Thanks Brent for the in depth analysis!

As I mentioned at the top: I was focusing on the usage examples not the
implementation. I've made compromises in this implementation to conform to
the existing protocols. Many of these compromises would probably be
addressed by SE0065 (
https://github.com/apple/swift-evolution/blob/master/proposals/0065-collections-move-indices.md
).

Answers inline.

On Saturday, 16 April 2016, Brent Royal-Gordon <brent at architechies.com>
wrote:

> > This is a clarification on what I meant (I haven't had much time to test
> it, but I think it's representative):
> >
> > https://gist.github.com/therealbnut/c223d90a34bb14448b65fc6cc0ec70ac
>
> There are a number of problems with this:
>
> * 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.

The main issue is that Dictionary can get/set an optional Value to
insert/remove values. Array doesn't currently have Optional get/set. Being
Optional doesn't make sense for an Array unless it's sparse. It would be
unexpected if an Array's `.endIndex != .count`.

I also think that, ideally, `Index == Key` for a Dictionary.

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.

* Generic `SequenceType` and `CollectionType` operations now use only the
> values, not the keys and values. That means that `Array(newDictionary)`
> gets you an array of values, `filter` returns an array of values, `reduce`
> operates only on the values, etc; all of these operations throw away the
> keys. That's not necessarily wrong, but I'm not sure that you're aware of
> it.


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).

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>


> * Your `enumerate` is similarly overloading by return type. It's also
> further confusing an already confused semantic. `enumerate` does not pair
> elements with their indices; it pairs them with integers starting at zero.
> This *happens* to correspond to their array indices, but that's not
> necessarily true of any other Collection. (I'm going to start another
> thread about this.)
>
> The overloaded return type is an unfortunate implementation detail, to fit
the existing protocols. The existing enumerate uses (Int,Value), as you
mentioned, i'm not sure if enumerate is changing after SE0065. Changing it
to (Index,Value) would solve the overload issue. I've seen a lot of array
code that uses enumerate() this way currently. I'm not sure what enumerate
is meant to be for if (Index,Value) is inappropriate.

Either way I think all collections would benefit from a property that
exposes a sequence of (Index,Value) pairs.

Basically, in this conception of Dictionary:
>
> * 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).

* 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.

* You still would need to name Dictionary-creating `map` and similar
> functions differently from their Array-generating cousins.


Only if you want map to return an array. There's a good argument for
Self.MapType etc. once we have generic associatedtype.


> * Iterating over keys and values together would require some kind of
> Dictionary-specific API, not something that was available on other
> collections or sequences.


I think that the existing `enumerate()` should do, if it is changed to
return (Index,Value) rather than (Int,Value). The downside is that
dictionaries would require `.enumerate()` added to many for loops, I agree
that this is not ideal. It may be that I'm misinterpreting enumerate, there
could probably be a shorter property name that would suffice.


> Maybe that would be an improvement, but I'm skeptical.
>
> Skeptical is good, it wasn't perfect, as long you have an open mind :)

--
> Brent Royal-Gordon
> Architechies
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160416/8566bde6/attachment.html>