Vague proposal: Extending coherence with workspaces

[withoutboats]

Exactly, Sequence is simply a special case of Map, from indices to items. Or a Map is simply a Sequence of key-value tuples. Depending on how you look at it, they’re really the same thing.

This not correct (at least without something approaching dependent types) because maps do not guarantee that if n is a key, pred(n) is also a key, and there is no way to express a refinement of the map interface which provides this guarantee. Iteration introduces some order, it might even be a non-arbitrary order (BTreeMap is an ordered map, by the way), but it does not mean that the keys in the map are all of the values in the range 0..len.

These are fundamentally different interfaces. It does not mean anything to ‘push’ to a map, and you can not insert at arbitrary indices greater than the length of a sequence.

I get the feeling that your division between Sequence and Map is based on formats such as JSON

Serialization, especially to formats like JSON, is a very obvious use case for the ability to provide blanket impls for both sequences and maps.

[Thiez]

Perhaps Sequence does not map to Map as well as the other way round, so I will focus on representing Map and Sequence. When turning a Map into a Sequence there is no need to guarantee that the keys all fall in the range 0..len. We simply assign the indices to the elements as they are yielded by iteration (e.g. with Iterator::enumerate) and the items in the sequence are the key-value pairs.

These are fundamentally different interfaces. It does not mean anything to ‘push’ to a map, and you can not insert at arbitrary indices greater than the length of a sequence.

Now we can push to a Map simply by push'ing the new key-value pair. To find something in our Map we simply look at the item in the Sequence with a matching key and the highest index.

At the end of the day I don’t think there is much point in being extremely strict with invariants for maps and sequences when serialization is involved, because anyone can easily edit the serialized data and break the invariants. I doubt we’ll agree on this, so perhaps it’s best to agree to disagree

[withoutboats]

The map in itself does not contain any notion of an index to its key value pairs. Iteration introduces a sequentiality to this only because iteration is performed in linear time and so events necessarily happen in sequence (parallel iterators have no such sequentiality). You can’t ‘push’ a key/value pair to a map because there’s no guarantee that key/value pair will be at the end of the map by virtue of being the most recently pushed item. Its also important that in sequences, repetition is allowed, which is not true of maps (if you try to view them as sequences of key/value pairs).

This conversation is wildly off-topic, it would be best to delay it to another time.

[GolDDranks]

Another proposal that should be orthogonal to the workspaces proposal but that might helps with coherence issues: Relax orphan rules for derived impls, aka “algorithmically derived opt-in blanket impls”: https://github.com/rust-lang/rfcs/issues/1553

[oli-obk]

to anyone interested, the “magical feature activation depending on available crates” idea is now an RFC by @withoutboats:

Automatic features.

[nikomatsakis]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.