Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/*:
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
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.