TypedHeterogeneousDictionaries.swift

/*:
 Joe Groff:

 > In a lot of the ways people use dictionaries/maps/hashtables, there's a type dependency between
 > the keys and values, but most mainstream typed languages provide homogeneously-typed maps.
 > Are there any that try to preserve more interesting type relationships between key and value?
 > https://twitter.com/jckarter/status/1278739951568314368

 > As one example, it's common for specific keys to be associated with specific types, like in
 > {"name": "Tanzy", "age": 13}, "name" should always map to a string, and "age" to a number.
 > Records/structs can model closed sets of keys with specific types, but what about open sets?
 > https://twitter.com/jckarter/status/1278739952138809344

 > In Swift, for instance, there are a lot of places where it'd be useful to have a map of
 > `KeyPath<T, U>` keys associated with `Something<U>` values, and right now you'd have to throw
 > away the type info in a [PartialKeyPath<T>: Any] dictionary.
 > https://twitter.com/jckarter/status/1278739952734363648

 This is essentially what the environment is in SwiftUI. An open set of strongly-typed key-value
 pairs.

 Another example from Hannes Oud: `[NSAttributedString.Key: Any]`
 https://twitter.com/hannesoid/status/1278766220418994178

 In Foundation, `URL.resourceValues(forKeys:)` "solves" this by returning a `URLResourceValues`
 struct, which you can then query with strongly-typed computed properties.
 https://developer.apple.com/documentation/foundation/url/1780058-resourcevalues

 Joe Groff:

 > Apple frameworks have a lot of these open sets. One way to model it would be to have a generic
 > key type that wraps the underlying key:
 >
 >     let name = Key<String>(“name”)
 >     let age = Key<Int>(“age”)
 >
 > https://twitter.com/jckarter/status/1279088247646216192

 Another example where this would be useful from Brent Royal-Gordon: a dictionary is used to hold a
 bag of, say, injected components of specific types:

 > At one point, I was playing around with a server-side framework that used what amounted to a
 > `[T.Type: T]` to allow composeable components to attach information to requests.
 > (Obviously it was actually an `[ObjectIdentifier: Any]`.)
 > https://twitter.com/brentdax/status/1278743486620069888

 Joe Groff:

 > pseudo-Swift:
 >
 >     struct Dict<Constraint: constraint(K, V)> {
 >       subscript<K, V>(element: K) -> V where Constraint(K, V)
 >     }
 >
 >     let x: Dict<(Int, String)> // homogeneous
 >     let y: Dict<<T> (KeyPath<Foo, T>, Something<T>)> // heterogeneous
 >
 > https://twitter.com/jckarter/status/1278747195022340097

 Vincent Esche:

 > TypeMap does something similar in Rust: https://github.com/reem/rust-typemap
 > https://twitter.com/regexident/status/1278769676429004801

 A related type theory concept is [row polymorphism](https://en.wikipedia.org/wiki/Row_polymorphism).
 The type of a row-polymorphic struct is the tuple of the name-type pairs of its member variables.
 Row-polymorphic record types allow us to write programs that operate on a section of a record
 (e.g. performing a 2D translation on a 3D point). Similar to structural typing in TypeScript.

 Joe Groff:

 > Part of what prompted this was me thinking how we could handle heterogeneous dynamic value-type
 > data structures without leaning on existential types
 > https://twitter.com/jckarter/status/1278773295756660736

 > Type system aside, heterogeneous maps also seem like good candidates for locality-friendly data
 > structures. I could imagine a hash table using variable bucket sizes to store different types
 > in-line, unlike a typical heterogeneous dictionary that would box each value
 > https://twitter.com/jckarter/status/1278739951568314368

 Adam Sharp:

 > TypeScript calls these Index Types, and provides a bunch of features for statically reasoning
 > about object keys and values https://typescriptlang.org/docs/handbook/advanced-types.html#index-types
 > https://twitter.com/sharplet/status/1278755063197040646

 Adam Roben:

 > Python has TypedDict: https://docs.python.org/3/library/typing.html#typing
 > https://twitter.com/aroben/status/1278798905635979265

 Python docs:

 > TypedDict creates a dictionary type that expects all of its instances to have a certain set of
 > keys, where each key is associated with a value of a consistent type. This expectation is not
 > checked at runtime but is only enforced by type checkers.
 */

// Type-safe Dictionaries by Slashmo: https://www.universalswift.blog/articles/type-safe-dictionaries/
// Good solution, but the problem is that the `Storage` type is not generic over the key type. I.e.
// you'd have to write a new type for every key category. To solve this, we need another protocol.
// I'm calling it `KeyGroup`:

protocol KeyGroup {}

protocol Key {
  associatedtype Value
  associatedtype Group: KeyGroup
}

struct Map<Keys: KeyGroup> {
  private var _storage: [ObjectIdentifier: Any] = [:]

  subscript<KeyType>(_ key: KeyType.Type) -> KeyType.Value? where KeyType: Key, KeyType.Group == Keys {
    get {
      guard let value = _storage[ObjectIdentifier(key)] else {
        return nil
      }
      return (value as! KeyType.Value)
    }
    set {
      _storage[ObjectIdentifier(key)] = newValue
    }
  }

  func hasValue<KeyType: Key>(key: KeyType.Type) -> Bool {
    _storage.index(forKey: ObjectIdentifier(key)) != nil
  }
}

// Usage:
enum UserKeys: KeyGroup {}

enum Name: Key {
  typealias Value = String
  typealias Group = UserKeys
}

enum Age: Key {
  typealias Value = Int?
  typealias Group = UserKeys
}

var map = Map<UserKeys>()
map[Name.self] = "Betty"
map[Age.self] = 42
map[Name.self]
map[Age.self]
map.hasValue(key: Age.self)
map[Age.self] = .none
map.hasValue(key: Age.self)

/*:
 Jordan Rose and Joe Groff came up with something similar:

 > maybe you could give `Record` a phantom type, and add a `ForRecord` assoc type to your keys,
 > which would allow it to constrain for `T: Key where ForRecord == PhantomType`
 > https://twitter.com/jckarter/status/1278781577774809088

 > Oh, that's not terrible. And that phantom type could be a key namespace. You may not even need
 > the RecordKey protocol at that point.
 >
 >     enum CarInfo {
 >       typealias Key<Value> = RecordKey<CarInfo, Value>
 >       let model = Key<String>("model")
 >       let year = Key<Int>("year")
 >     }
 >
 > https://twitter.com/UINT_MIN/status/1278789029694078976
 */