[swift-evolution] Dictionary Enhancements

[Nate Cook]

Hi Jon,

Thank you for the feedback, this is really valuable! A couple questions below.

> 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 <mailto: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 <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 <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.
> 
> I would also like to see an in-place version as well.
> 
> 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.

Do you have any examples you can share where you use the key in this type of map? I'm not contesting its usefulness; it would just be helpful to see some real-world usage.

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

I think the uses you're describing are handled by the merging initializer proposed in SE-100:
	https://github.com/apple/swift-evolution/blob/master/proposals/0100-add-sequence-based-init-and-merge-to-dictionary.md <https://github.com/apple/swift-evolution/blob/master/proposals/0100-add-sequence-based-init-and-merge-to-dictionary.md>

For example, you can use a combining closure to select specific elements when the keys collide:

let duplicates: DictionaryLiteral = ["a": 1, "b": 2, "a": 3, "b": 4]
// Using the first value only
Dictionary(merging: duplicates, combine: { (first, _) in first })    // ["b": 2, "a": 1]
// Using the maximum value
Dictionary(merging: duplicates, combine: max)      // ["b": 4, "a": 3]

or to calculate the frequencies of values in a sequence:

extension Sequence where Iterator.Element: Hashable {
    func frequencies() -> [Iterator.Element: Int] {
        return Dictionary(merging: self.lazy.map { v in (v, 1) }, combine: +)
    }
}
[1, 2, 2, 3, 1, 2, 4, 5, 3, 2, 3, 1].frequencies()
// [2: 4, 4: 1, 5: 1, 3: 3, 1: 3]

Could you take a look and see if that provides the functionality you're looking for?

> 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.
> 
> 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!
Nate
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170217/02d611c4/attachment.html>