[swift-evolution] Dictionary Enhancements

[Matthew Johnson]

Sent from my iPad

> On Feb 17, 2017, at 8:50 PM, Jonathan Hull via swift-evolution <swift-evolution at swift.org> wrote:
> 
> Thoughts inline.
> 
>> On Feb 16, 2017, at 4:26 PM, Ben Cohen via swift-evolution <swift-evolution at swift.org> wrote:
>> 
>> Hi swift-evolution,
>> 
>> Following up on Ted’s post regarding the opening up of stage 2, I’m starting a thread to discuss improvements to the Dictionary type.
>> 
>> Here is a list of commonly requested changes/enhancements to Dictionary, all of which would probably be appropriate to put together into a single evolution proposal:
>> 
>> init from/merge in a Sequence of Key/Value pairs (already raised as SE-100: https://github.com/apple/swift-evolution/blob/master/proposals/0100-add-sequence-based-init-and-merge-to-dictionary.md).
> +1. I have wanted this since Swift 1.
> 
>> make the Values view collection a MutableCollection (as in this PR: https://github.com/apple/swift-evolution/pull/555).
> I think Nate’s proposal covers this case well.
> 
>> Add a defaulting subscript get (e.g. counts[key, default: 0] += 1 or grouped(key, default:[]].append(value)).
> I am indifferent to this. I am happy using ??.  I guess it could be slightly more efficient because it avoids wrapping and unwrapping the optional.
> 
>> Add a group by-like init to create a Dictionary<K,[V]> from a sequence of V and a closure (V)->K.
> +1. I would use this.
> 
>> Add Dictionary.filter to return a Dictionary.
> +1.
> 
>> Add Dictionary.mapValues to return a Dictionary (can be more efficiently implemented than composition as the storage layout remains the same).
> +1000.  I have also been asking for this since the beginning.  I built my own version (and use it frequently), but as you say, the standard library can do it much more efficiently.

Agree this is a big one.  Hopefully if we ever get higher-kinded types we might also have a way to map this method (pun intended) to a Dictionary implementation of Functor.

> 
> I would also like to see an in-place version as well.

This would be useful for transformations mapping values to the same type.

> 
> One design detail. Even though it is only mapping the values, I would like it to pass the key to the closure as well.  It occasionally figures in to the mapping logic.

I can see how this could be useful but it should be an additional overload.  I want to be able to give mapValues any function that just takes the value type as input.

> 
> 
>> Add capacity property and reserveCapacity() method.
> +0.5. I could see it being useful occasionally.
> 
>> Have Dictionary.removeAtIndex return the Index of the next entry.
> No opinion on this.
> 
>> (once we have conditional conformance) Make dictionaries with Equatable values Equatable.
> +1
> 
>> Please reply here with any comments or questions on the above list, or any additions you believe are important that are missing from it.
>> 
> I would also like to see a version of map which returns a dictionary and handles key collisions:
> 
> 	let newDict = myDict.map(collision: {k,v1,v2 in v2}) { (k,v) in ... }
> 
> The collision parameter would take a throwing closure and handle the case of a key conflict (by returning the value to use, throwing, or trapping).  It would have a default value so that it would only have to be specified if a different behavior was desired.  
> 
> In advanced cases, the collision could be used to accumulate values together.  Because of this, I would actually like to see this on *collection* (not just dictionary).  The map closure is handed each element of the sequence (which in the case of dictionary is a key/value tuple), and expects a return value of a key/value tuple.  The collision block is called when a key is returned which has already been used to figure out what value to use.  This might choose a winner, or it could act like reduce, building a value from the components.
> 
> As a concrete example of what this allows, I could take in an array of words/strings [“apple”, “aardvark”, …] and then do the following to get a count of how many words start with each letter:
> 	
> 	let letterFrequency = words.map(collision:{$1+$2}) { (String($0.characters.first ?? “”) ,1)}
> 	
> 	print(letterFrequency[“a”]) //number of words starting with “a"
> 
> I am ok using a term other than ‘map' if that is easier on the compiler, but I would like this functionality.  At the simple end, it allows map functionality for both keys and values.  At the advanced end, it acts as a categorizing reduce over a sequence/collection.

This is a very interesting idea.

> 
> You can even trivially implement the proposed groupBy with it (this is on Collection, but you could do an init on dict the same way):
> 
> 	func grouped<K>(by categorizer: (Element)->K ) -> [K:Element] {
> 		return self.map(collision:{$1+$2}) {(categorizer($0), [$0])}
> 	}
> 
> 
> Thanks,
> Jon
> 
> 
>> All methods added to the standard library increase complexity, so need a strong justification to reduce the risk of API sprawl. When requesting additions/modifications, please keep the following questions in mind:
>> 
>> Is the suggested addition a common operation that many would find useful? Can it be flexible enough to cover different needs?
>> Will it encourage good practice? Might it be misused or encourage anti-patterns?
>> Can the operation be composed simply from existing std lib features? Is that composition intuitive/readable? 
>> Is writing the equivalent by hand hard to get right? Are there common correctness traps that this addition would help avoid?
>> Is writing the equivalent by hand hard to make efficient? Are there common performance traps that this addition would help avoid?
>> Might a native implementation be able to execute more efficiently, by accessing internals, than the equivalent implementation using public APIs?
>> As he has already written up SE-100 and another Dictionary proposal, Nate Cook has kindly offered to collate a new omnibus proposal for Dictionary, which will then get pitched here.
>> 
>> I will send another email about enhancements to Sequence/Collection algorithms shortly.
>> 
>> Thanks!
>> 
>> Ben
>> 
>> 
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170217/0ee36fa3/attachment.html>