Skip to content

Latest commit

 

History

History
516 lines (374 loc) · 24 KB

0165-dict.md

File metadata and controls

516 lines (374 loc) · 24 KB
Raw

Dictionary & Set Enhancements

Introduction

This proposal comprises a variety of commonly (and less commonly) suggested improvements to the standard library's Dictionary type, from merging initializers to dictionary-specific filter and mapValues methods. The proposed additions to Dictionary, and the corresponding changes to Set, are detailed in the sections below.

1. Merging initializers and methods

The Dictionary type should allow initialization from a sequence of (Key, Value) tuples and offer methods that merge a sequence of (Key, Value) tuples into a new or existing dictionary, using a closure to combine values for duplicate keys.

Array and Set both have initializers that create a new instance from a sequence of elements. The Array initializer is useful for converting other sequences and collections to the "standard" collection type, while the Set initializer is essential for recovering set operations after performing any functional operations on a set. For example, filtering a set produces a collection without any set operations available.

let numberSet = Set(1 ... 100)
let fivesOnly = numberSet.lazy.filter { $0 % 5 == 0 }

fivesOnly is a LazyFilterCollection<Set<Int>> instead of a Set—sending that back through the Set sequence initializer restores the expected methods.

let fivesOnlySet = Set(numberSet.lazy.filter { $0 % 5 == 0 })
fivesOnlySet.isSubsetOf(numberSet) // true

Dictionary, on the other hand, has no such initializer, so a similar operation leaves no room to recover dictionary functionality without building a mutable Dictionary via iteration or functional methods. These techniques also don't support type inference from the source sequence, increasing verbosity.

let numberDictionary = ["one": 1, "two": 2, "three": 3, "four": 4]
let evenOnly = numberDictionary.lazy.filter { (_, value) in
    value % 2 == 0
}

var viaIteration: [String: Int] = [:]
for (key, value) in evenOnly {
    viaIteration[key] = value
}

let viaReduce: [String: Int] = evenOnly.reduce([:]) { (cumulative, kv) in
    var dict = cumulative
    dict[kv.key] = kv.value
    return dict
}

Beyond initialization, Array and Set both also provide a method to add a new block of elements to an existing collection. Array provides this via append(contentsOf:) for the common appending case or replaceSubrange(_:with:) for general inserting or replacing, while the unordered Set type lets you pass any sequence to unionInPlace(_:) to add elements to an existing set.

Once again, Dictionary has no corresponding API -- looping and adding elements one at a time as shown above is the only way to merge new elements into an existing dictionary.

Proposed solution

This proposal puts forward two new ways to convert (Key, Value) sequences to dictionary form: an initializer and a set of merging APIs that handle input data with duplicate keys.

Sequence-based initializer

The proposed solution would add a new initializer to Dictionary that accepts any sequence of (Key, Value) tuple pairs.

init<S: Sequence where S.Iterator.Element == (key: Key, value: Value)>(
    uniqueKeysWithValues: S)

With the proposed initializer, creating a Dictionary instance from a sequence of key/value pairs is as easy as creating an Array or Set:

let viaProposed = Dictionary(uniqueKeysWithValues: evenOnly)

Like Array.init(_:) and Set.init(_:), this is a full-width initializer. To ensure this, the initializer has a precondition that each key in the supplied sequence is unique, and traps whenever that condition isn't met. When duplicate keys are possible in the input, the merging initializer described in the next section must be used instead.

The new initializer allows for some convenient uses that aren't currently possible.

  • Initializing from a DictionaryLiteral (the type, not an actual literal)

    let literal: DictionaryLiteral = ["a": 1, "b": 2, "c": 3, "d": 4]
let dictFromDL = Dictionary(uniqueKeysWithValues: literal)

  • Converting an array to an indexed dictionary (popular on the thread)

    let names = ["Cagney", "Lacey", "Bensen"]
let dict = Dictionary(uniqueKeysWithValues: names.enumerated().map { (i, val) in (i + 1, val) })
// [2: "Lacey", 3: "Bensen", 1: "Cagney"]

  • Initializing from a pair of zipped sequences (examples abound)

    let letters = "abcdef".characters.lazy.map(String.init)
let dictFromZip = Dictionary(uniqueKeysWithValues: zip(letters, 1...10))
// ["b": 2, "e": 5, "a": 1, "f": 6, "d": 4, "c": 3]

    This particular use is currently blocked by SR-922. As a workaround, add .map {(key: $0, value: $1)}.

Merging initializer and methods

Creating a Dictionary from a dictional literal checks the keys for uniqueness, trapping on a duplicate. The sequence-based initializer shown above has the same requirement.

let duplicates: DictionaryLiteral = ["a": 1, "b": 2, "a": 3, "b": 4]
let letterDict = Dictionary(uniqueKeysWithValues: duplicates)
// error: Duplicate key found: "a"

Because some use cases can be forgiving of duplicate keys, this proposal includes a second new initializer. This initializer allows the caller to supply, along with the sequence, a combining closure that's called with the old and new values for any duplicate keys.

init<S: Sequence>(
    _ keysAndValues: S,
    uniquingKeysWith combine: (Value, Value) throws -> Value
) rethrows where S.Iterator.Element == (key: Key, value: Value)

This example shows how one could keep the first value of all those supplied for a duplicate key.

let letterDict2 = Dictionary(duplicates, uniquingKeysWith: { (first, _) in first })
// ["b": 2, "a": 1]

Or the largest value for any duplicate keys.

let letterDict3 = Dictionary(duplicates, uniquingKeysWith: max)
// ["b": 4, "a": 3]

At other times the merging initializer could be used to combine values for duplicate keys. Donnacha Oisín Kidney wrote a neat frequencies() method for sequences as an example of such a use in the thread.

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

This proposal also includes new mutating and non-mutating methods for Dictionary that merge the contents of a sequence of (Key, Value) tuples into an existing dictionary, merge(_:uniquingKeysWith:) and merging(_:uniquingKeysWith:).

mutating func merge<S: Sequence>(
    _ other: S,
    uniquingKeysWith combine: (Value, Value) throws -> Value
) rethrows where S.Iterator.Element == (key: Key, value: Value)

func merging<S: Sequence>(
    _ other: S,
    uniquingKeysWith combine: (Value, Value) throws -> Value
) rethrows -> [Key: Value] where S.Iterator.Element == (key: Key, value: Value)

As above, there are a wide variety of uses for the merge.

// Adding default values
let defaults: [String: Bool] = ["foo": false, "bar": false, "baz": false]
var options: [String: Bool] = ["foo": true, "bar": false]
options.merge(defaults) { (old, _) in old }
// options is now ["foo": true, "bar": false, "baz": false]

// Summing counts repeatedly
var bugCounts: [String: Int] = ["bees": 9, "ants": 112, ...]
while bugCountingSource.hasMoreData() {
    bugCounts.merge(bugCountingSource.countMoreBugs(), uniquingKeysWith: +)
}

2. Key-based subscript with default value

Another common challenge with dictionaries is iteratively making changes to key/value pairs that may or may not already be present. For example, to iteratively add count the frequencies of letters in a string, one might write something like the following:

let source = "how now brown cow"
var frequencies: [Character: Int] = [:]
for c in source.characters {
    if frequencies[c] == nil {
        frequencies[c] = 1
    } else {
        frequencies[c]! += 1
    }
}

Testing for nil and assigning through the force unwrapping operator are awkward at best for such a common operation. Furthermore, the Optional<Value> return type of the current keyed subscript complicates efficiencies that could be gained for this type of modify action under a future ownership model.

Proposed solution

A keyed subscript with a default value neatly simplifies this usage. Instead of checking for nil, one can pass the default value along with the key as a default subscript parameter.

let source = "how now brown cow"
var frequencies: [Character: Int] = [:]
for c in source.characters {
    frequencies[c, default: 0] += 1
}

The return type of this subscript is a non-optional Value. Note that accessing the subscript as a getter does not store the default value in the dictionary—the following two lines are equivalent:

let x = frequencies["a", default: 0]
let y = frequencies["a"] ?? 0

3. Dictionary-specific map and filter

The standard map and filter methods, while always useful and beloved, aren't ideal when applied to dictionaries. In both cases, the desired end-result is frequently another dictionary instead of an array of key-value pairs—even with the sequence-based initializer proposed above this is an inefficient way of doing things.

Additionally, the standard map method doesn't gracefully support passing a function when transforming only the values of a dictionary. The transform function must accept and return key/value pairs, necessitating a custom closure in nearly every case.

Assuming the addition of a sequence-based initializer, the current filter and map look like the following:

let numbers = ["one": 1, "two": 2, "three": 3, "four": 4]
let evens = Dictionary(numbers.lazy.filter { $0.value % 2 == 0 })!
// ["four": 4, "two": 2]
let strings = Dictionary(numbers.lazy.map { (k, v) in (k, String(v)) })!
// ["three": "3", "four": "4", "one": "1", "two": "2"]

Proposed solution

This proposal adds two new methods for Dictionary:

  1. A mapValues method that keeps a dictionary's keys intact while transforming the values. Mapping a dictionary's key/value pairs can't always produce a new dictionary, due to the possibility of key collisions, but mapping only the values can produce a new dictionary with the same underlying layout as the original.

    let strings = numbers.mapValues(String.init)
// ["three": "3", "four": "4", "one": "1", "two": "2"]

  2. A Dictionary-returning filter method. While transforming the keys and values of a dictionary can result in key collisions, filtering the elements of a dictionary can at worst replicate the entire dictionary.

    let evens = numbers.filter { $0.value % 2 == 0 }
// ["four": 4, "two": 2]

Both of these can be made significantly more efficient than their Sequence-sourced counterparts. For example, the mapValues method can simply copy the portion of the storage that holds the keys to the new dictionary before transforming the values.

4. Visible dictionary capacity

As you add elements to a dictionary, it automatically grows its backing storage as necessary. This reallocation is a significant operation—unlike arrays, where the existing elements can be copied to a new block of storage en masse, every key/value pair must be moved over individually, recalculating the hash value for the key to find its position in the larger backing buffer.

While dictionaries uses an exponential growth strategy to make this as efficient as possible, beyond the init(minimumCapacity:) initializer they do not expose a way to reserve a specific capacity. In addition, adding a key/value pair to a dictionary is guaranteed not to invalidate existing indices as long as the capacity doesn't change, yet we don't provide any way of seeing a dictionary's current or post-addition capacity.

Proposed solution

Dictionary should add a capacity property and a reserveCapacity(_:) method, like those used in range-replaceable collections. The capacity of a dictionary is the number of elements it can hold without reallocating a larger backing storage, while calling reserveCapacity(_:) allocates a large enough buffer to hold the requested number of elements without reallocating.

var numbers = ["one": 1, "two": 2, "three": 3, "four": 4]
numbers.capacity   // 6
numbers.reserveCapacity(20)
numbers.capacity   // 24

Because hashed collections use extra storage capacity to reduce the likelihood and cost of collisions, the value of the capacity property won't be equal to the actual size of the backing storage. Likewise, the capacity after calling reserveCapacity(_:) will be at least as large as the argument, but usually larger. (In its current implementation, Dictionary always has a power of 2-sized backing storage.)

5. Grouping sequence elements

As a final Dictionary-related issue, grouping elements in a sequence by some computed key is a commonly requested addition that we can add as part of this omnibus proposal. Call a new Dictionary(grouping:by:) initializer with a closure that converts each value in a sequence to a hashable type T; the result is a dictionary with keys of type T and values of type [Iterator.Element].

let names = ["Patti", "Aretha", "Anita", "Gladys"]

// By first letter
Dictionary(grouping: names, by: { $0.characters.first! })
// ["P": ["Patti"], "G": ["Gladys"], "A": ["Aretha", "Anita"]]

// By name length
Dictionary(grouping: names) { $0.utf16.count }
// [5: ["Patti", "Anita"], 6: ["Aretha", "Gladys"]]

6. Apply relevant changes to Set

As the Set and Dictionary types are similar enough to share large chunks of their implementations, it makes sense to look at which of these Dictionary enhancements can also be applied to Set. Of the symbols proposed above, the following additions would also be useful and appropriate for the Set type:

  • Add a Set-specific filter method that returns a new set—this would function essentially as a predicate-based intersection method.
  • Add a capacity property and reserveCapacity() method, for the reasons listed above.

Detailed design

With the exception of the proposed capacity property and method, the proposed additions to Dictionary, Set, and Sequence are available in this Swift Sandbox. Note that this prototype is not a proposed implementation; rather a way to try out the behavior of the proposed changes.

Collected in one place, these are the new APIs for Dictionary, Set, and Sequence:

struct Dictionary<Key: Hashable, Value> {
    typealias Element = (key: Key, value: Value)

    // existing declarations

    /// Creates a new dictionary using the key/value pairs in the given sequence.
    /// If the given sequence has any duplicate keys, the result is `nil`.
    init<S: Sequence>(uniqueKeysWithValues: S) where S.Iterator.Element == Element

    /// Creates a new dictionary using the key/value pairs in the given sequence,
    /// using a combining closure to determine the value for any duplicate keys.
    init<S: Sequence>(
        _ keysAndValues: S,
        uniquingKeysWith combine: (Value, Value) throws -> Value
    ) rethrows where S.Iterator.Element == Element

    /// Creates a new dictionary where the keys are the groupings returned by
    /// the given closure and the values are arrays of the elements that
    /// returned each specific key.
    init<S: Sequence>(
    	grouping values: S,
	by keyForValue: (S.Iterator.Element) throws -> Key
    ) rethrows where Value == [S.Iterator.Element]

    /// Merges the key/value pairs in the given sequence into the dictionary,
    /// using a combining closure to determine the value for any duplicate keys.
    mutating func merge<S: Sequence>(
        _ other: S,
        uniquingKeysWith combine: (Value, Value) throws -> Value
    ) rethrows where S.Iterator.Element == Element

    /// Returns a new dictionary created by merging the key/value pairs in the
    /// given sequence into the dictionary, using a combining closure to determine
    /// the value for any duplicate keys.
    func merging<S: Sequence>(
        _ other: S,
        uniquingKeysWith combine: (Value, Value) throws -> Value
    ) rethrows -> [Key: Value] where S.Iterator.Element == Element

    /// Accesses the element with the given key, or the specified default value,
    /// if the dictionary doesn't contain the given key.
    subscript(key: Key, default defaultValue: Value) -> Value { get set }

    /// Returns a new dictionary containing the key/value pairs that satisfy
    /// the given predicate.
    func filter(_ isIncluded: (Key, Value) throws -> Bool) rethrows -> [Key: Value]

    /// Returns a new dictionary containing the existing keys and the results of
    /// mapping the given closure over the dictionary's values.
    func mapValues<T>(_ transform: (Value) throws -> T) rethrows -> [Key: T]

    /// The number of key/value pairs that can be stored by the dictionary without
    /// reallocating storage.
    var capacity: Int { get }

    /// Ensures that the dictionary has enough storage for `capacity` key/value
    /// pairs.
    var reserveCapacity(_ capacity: Int)
}

struct Set<Element: Hashable> {
    // existing declarations

    /// Returns a new set containing the elements that satisfy the given predicate.
    func filter(_ isIncluded: (Element) throws -> Bool) rethrows -> Set

    /// The number of elements that can be stored by the set without
    /// reallocating storage.
    var capacity: Int { get }

    /// Ensures that the set has enough storage for `capacity` elements.
    var reserveCapacity(_ capacity: Int)
}

Alternatives Considered

  • An earlier version of this proposal declared the first merging initializer as failable, returning nil when a sequence with duplicate keys was passed. That initializer is really only appropriate when working with known unique keys, however, as there isn't a feasible recovery path when there can be duplicate keys. That leaves two possibilities:

    1. The source input can never have duplicate keys, and the programmer has to write ! or unwrap in some other way, or
    2. The source input can have duplicate keys, in which case the programmer should be using init(merging:mergingValues:) instead.

  • An earlier version of this proposal included the addition of two new top-level functions to the standard library: first(_:_:) and last(_:_:), which return their first and last arguments, respectively. These new functions would be passed instead of a custom closure to a merging method or initializer:

     let firstWins = Dictionary(merging: duplicates, mergingValues: first)
 // ["b": 2, "a": 1]

 let lastWins = Dictionary(merging: duplicates, mergingValues: last)
 // ["b": 4, "a": 3]

    As an alternative to the first(_:_:) and last(_:_:) functions, at the cost of three additional overloads for the merging initializer and methods, we could allow users to specify the useFirst and useLast cases of a MergeCollisionStrategy enumeration.

     extension Dictionary {
     /// The strategy to use when merging a sequence of key-value pairs into a dictionary.
     enum MergeCollisionStrategy {
         /// If there is more than one instance of a key in the sequence to merge, use
         /// only the first value for the dictionary.
         case useFirst
         /// If there is more than one instance of a key in the sequence to merge, use
         /// only the last value for the dictionary.
         case useLast
     }

     init<S: Sequence>(
         merging keysAndValues: S,
         mergingValues strategy: MergeCollisionStrategy
     )

     // other merging overloads
 }

    In use, this overload would look similar to the functional version, but may aid in discoverability:

     let firstWins = Dictionary(merging: duplicates, mergingValues: .useFirst)
 // ["b": 2, "a": 1]

 let lastWins = Dictionary(merging: duplicates, mergingValues: .useLast)
 // ["b": 4, "a": 3]

  • An earlier version of this proposal included a change to both collections' remove(at:) method, such that it would return both the removed element and the next valid index in the iteration sequence. This change lets a programmer write code that would remove elements of a dictionary or a set in place, which can't currently be done with as much efficiency due to index invalidation:

    var i = dict.startIndex
while i != dict.endIndex {
    if shouldRemove(dict[i]) {
        (_, i) = dict.remove(at: i)
    } else {
        dict.formIndex(after: &i)
    }
}

    This change to remove(at:) has been deferred to a later proposal that can better deal with the impact on existing code.

  • The reviewed version of this proposal had different spelling of the merging initializers and methods:

    init<S: Sequence where S.Iterator.Element == (key: Key, value: Value)>(
    _ keysAndValues: S)

init<S: Sequence>(
    merging keysAndValues: S,
    mergingValues combine: (Value, Value) throws -> Value
) rethrows where S.Iterator.Element == (key: Key, value: Value)

mutating func merge<S: Sequence>(
    _ other: S,
    mergingValues combine: (Value, Value) throws -> Value
) rethrows where S.Iterator.Element == (key: Key, value: Value)

func merged<S: Sequence>(
    with other: S,
    mergingValues combine: (Value, Value) throws -> Value
) rethrows -> [Key: Value] where S.Iterator.Element == (key: Key, value: Value)

    In addition, the Dictionary(grouping:by:) initializer was proposed as a grouped(by:) method on the Sequence protocol. The rationale for accepting the proposal explains the reasons for these changes.

Source compatibility

All the proposed additions are purely additive and should impose only a minimal source compatibility burden. The addition of same-type returning filter(_:) methods to Dictionary and Set could cause problems if code is relying on the previous behavior of returning an array. For example, the following code would break after this change:

let digits = Set(0..<10)
let evens = digits.filter { $0 % 2 == 0 }
functionThatTakesAnArray(evens)

To mitigate the impact of this on code compiled in Swift 3 mode, Dictionary and Set will have an additional overload of the Array-returning filter(_:) that is marked as obsoleted in Swift 4. This will allow Swift 3 code to continue to compile and work as expected:

extension Set {
    @available(swift, obsoleted: 4)
    func filter(_ isIncluded: (Element) throws -> Bool) rethrows -> [Element]

    @available(swift, introduced: 4)
    func filter(_ isIncluded: (Element) throws -> Bool) rethrows -> Set<Element>
}