Eliminate inconsistencies among primary collection types

Evolution Discussion
1

A. When trying to declare nested collection types an inconsistency
   is unveiled:

A.1. “Array” as outer type allows for every collection type as inner
     type (“Int” used as a placeholder for “some other type”):

    let test_aa: Array<Array<Int>> =
        // ok

    let test_as: Array<Set<Int>> =
        // ok

    let test_ad: Array<Dictionary<Int, Int>> =
        // ok

A.2. “Set” as outer type allows for “Set” as inner type only:

    let test_sa: Set<Array<Int>> =
        // compile time error “Type 'Array<Int>' does not conform to
        // protocol 'Hashable'”

    let test_ss: Set<Set<Int>> =
        // ok

    let test_sd: Set<Dictionary<Int, Int>> =
        // compile time error “Type 'Dictionary<Int, Int>' does not
        // conform to protocol 'Hashable'”

A.3. The same is true for “Dictionary” as outer type:

    let test_da: Dictionary<Array<Int>, Int> = [:]
        // compile time error “Type 'Array<Int>' does not conform to
        // protocol 'Hashable'”

    let test_ds: Dictionary<Set<Int>, Int> = [:]
        // ok

    let test_dd: Dictionary<Dictionary<Int, Int>, Int> = [:]
        // compile time error “Type 'Dictionary<Int, Int>' does not
        // conform to protocol 'Hashable'”

B. When letting Swift infer the type of collections of “Array” from
   literals another inconsistency comes to light:

B.1. “Array” as outer type behaves IMHO perfectly:

    var testArray = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
    print(testArray.dynamicType)
        // prints “Array<Array<Int>>”
    testArray.append( [ 1, "five", 25, 625 ] );
        // compile time error “Cannot convert value of 'String' to
        // expected element type 'Int'”; type safe

B.2. “Set” as outer type works but there is no type safety:

    var testSet: Set = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
    print(testSet.dynamicType)
        // prints “Set<NSArray>”
    testSet.insert( [ 1, "five", 25, 625 ] )
        // neither run time nor compile time errors; no type safety

B.3. The same goes for “Dictionary” as outer type:

    var testDictionary = [
        [ 1, 2, 4, 8 ]: "Powers of Two",
        [ 1, 3, 9, 27 ]: "Powers of Three",
    ]
    print(testDictionary.dynamicType)
        // prints "Dictionary<NSArray, String>"
    testDictionary[ [ 1, "five", 25, 625 ] ] = "Powers of Five"
        // neither run time nor compile time errors; no type safety

— — - Wolfgang H.

2

AFAICT this is all due to the lack of a compiler feature called
“constrained conformances,” which we'd like to implement but don't have
yet.

···

on Fri Apr 29 2016, "Wolfgang H. via swift-evolution" <swift-evolution@swift.org> wrote:

A. When trying to declare nested collection types an inconsistency
   is unveiled:

--
Dave

3

I'm not sure I understand the inconsistency you see. Set and Dictionary
require hashable values and keys, respectively. That's just in the nature
of what these types are. Do you want Set itself to conform to Hashable?

···

On Fri, Apr 29, 2016 at 12:57 Wolfgang H. via swift-evolution < swift-evolution@swift.org> wrote:

A. When trying to declare nested collection types an inconsistency
   is unveiled:

A.1. “Array” as outer type allows for every collection type as inner
     type (“Int” used as a placeholder for “some other type”):

    let test_aa: Array<Array<Int>> =
        // ok

    let test_as: Array<Set<Int>> =
        // ok

    let test_ad: Array<Dictionary<Int, Int>> =
        // ok

A.2. “Set” as outer type allows for “Set” as inner type only:

    let test_sa: Set<Array<Int>> =
        // compile time error “Type 'Array<Int>' does not conform to
        // protocol 'Hashable'”

    let test_ss: Set<Set<Int>> =
        // ok

    let test_sd: Set<Dictionary<Int, Int>> =
        // compile time error “Type 'Dictionary<Int, Int>' does not
        // conform to protocol 'Hashable'”

A.3. The same is true for “Dictionary” as outer type:

    let test_da: Dictionary<Array<Int>, Int> = [:]
        // compile time error “Type 'Array<Int>' does not conform to
        // protocol 'Hashable'”

    let test_ds: Dictionary<Set<Int>, Int> = [:]
        // ok

    let test_dd: Dictionary<Dictionary<Int, Int>, Int> = [:]
        // compile time error “Type 'Dictionary<Int, Int>' does not
        // conform to protocol 'Hashable'”

B. When letting Swift infer the type of collections of “Array” from
   literals another inconsistency comes to light:

B.1. “Array” as outer type behaves IMHO perfectly:

    var testArray = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
    print(testArray.dynamicType)
        // prints “Array<Array<Int>>”
    testArray.append( [ 1, "five", 25, 625 ] );
        // compile time error “Cannot convert value of 'String' to
        // expected element type 'Int'”; type safe

B.2. “Set” as outer type works but there is no type safety:

    var testSet: Set = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
    print(testSet.dynamicType)
        // prints “Set<NSArray>”
    testSet.insert( [ 1, "five", 25, 625 ] )
        // neither run time nor compile time errors; no type safety

B.3. The same goes for “Dictionary” as outer type:

    var testDictionary = [
        [ 1, 2, 4, 8 ]: "Powers of Two",
        [ 1, 3, 9, 27 ]: "Powers of Three",
    ]
    print(testDictionary.dynamicType)
        // prints "Dictionary<NSArray, String>"
    testDictionary[ [ 1, "five", 25, 625 ] ] = "Powers of Five"
        // neither run time nor compile time errors; no type safety

— — - Wolfgang H.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

4

The only way to do this would be to require a hashing closure as an alternative to requiring Hashable, which is certainly do-able, but would be just as inconsistent.

I think the real problem is that Set and Dictionary are just types, but really they should conform to some kind of protocol instead, as it’s entirely conceivable to want to implement a key/value type that uses a tree structure for storage, in which case Hashable isn’t a requirement (but Comparable might be).

The solution therefore is to define general purpose Set and Map protocols, and maybe rename Set to HashSet or something, so that we have a similar distinction as is the case between CollectionType (protocol) and Array (implementing type). I’ve been trying to do this retroactively to implement some specialised map-types, but it leads to all kinds of compiler issues since Dictionary is being extended in a somewhat unusual way, I expect Set might have similar issues, so it would be better if the protocols were official.

···

On 29 Apr 2016, at 18:57, Wolfgang H. via swift-evolution <swift-evolution@swift.org> wrote:

A. When trying to declare nested collection types an inconsistency
  is unveiled:

A.1. “Array” as outer type allows for every collection type as inner
    type (“Int” used as a placeholder for “some other type”):

   let test_aa: Array<Array<Int>> =
       // ok

   let test_as: Array<Set<Int>> =
       // ok

   let test_ad: Array<Dictionary<Int, Int>> =
       // ok

A.2. “Set” as outer type allows for “Set” as inner type only:

   let test_sa: Set<Array<Int>> =
       // compile time error “Type 'Array<Int>' does not conform to
       // protocol 'Hashable'”

   let test_ss: Set<Set<Int>> =
       // ok

   let test_sd: Set<Dictionary<Int, Int>> =
       // compile time error “Type 'Dictionary<Int, Int>' does not
       // conform to protocol 'Hashable'”

A.3. The same is true for “Dictionary” as outer type:

   let test_da: Dictionary<Array<Int>, Int> = [:]
       // compile time error “Type 'Array<Int>' does not conform to
       // protocol 'Hashable'”

   let test_ds: Dictionary<Set<Int>, Int> = [:]
       // ok

   let test_dd: Dictionary<Dictionary<Int, Int>, Int> = [:]
       // compile time error “Type 'Dictionary<Int, Int>' does not
       // conform to protocol 'Hashable'”

B. When letting Swift infer the type of collections of “Array” from
  literals another inconsistency comes to light:

B.1. “Array” as outer type behaves IMHO perfectly:

   var testArray = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
   print(testArray.dynamicType)
       // prints “Array<Array<Int>>”
   testArray.append( [ 1, "five", 25, 625 ] );
       // compile time error “Cannot convert value of 'String' to
       // expected element type 'Int'”; type safe

B.2. “Set” as outer type works but there is no type safety:

   var testSet: Set = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
   print(testSet.dynamicType)
       // prints “Set<NSArray>”
   testSet.insert( [ 1, "five", 25, 625 ] )
       // neither run time nor compile time errors; no type safety

B.3. The same goes for “Dictionary” as outer type:

   var testDictionary = [
       [ 1, 2, 4, 8 ]: "Powers of Two",
       [ 1, 3, 9, 27 ]: "Powers of Three",
   ]
   print(testDictionary.dynamicType)
       // prints "Dictionary<NSArray, String>"
   testDictionary[ [ 1, "five", 25, 625 ] ] = "Powers of Five"
       // neither run time nor compile time errors; no type safety

— — - Wolfgang H.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

5

Inconsistency A. is that “Set” currently is the only collection type conforming to protocol 'Hashable'”. IMHO both “Array” and “Dictionary” should conform to protocol “Hashable”, too.

Inconsistency B. is that “Array<Int>” is typesafe if used as element of an “Array” but is non-typesafe if used as element of “Set” or “Dictionary”. The non-typesafety may result from the mapping of “Array<Int>” to “NSArray“.

- - - Wolfgang H.

···

Am 2016-04-29 17/Fr um 20:18 schrieb Xiaodi Wu - xiaodi.wu@gmail.com:

I'm not sure I understand the inconsistency you see. Set and Dictionary require hashable values and keys, respectively. That's just in the nature of what these types are. Do you want Set itself to conform to Hashable?

On Fri, Apr 29, 2016 at 12:57 Wolfgang H. via swift-evolution <swift-evolution@swift.org> wrote:

A. When trying to declare nested collection types an inconsistency
  is unveiled:

A.1. “Array” as outer type allows for every collection type as inner
    type (“Int” used as a placeholder for “some other type”):

   let test_aa: Array<Array<Int>> =
       // ok

   let test_as: Array<Set<Int>> =
       // ok

   let test_ad: Array<Dictionary<Int, Int>> =
       // ok

A.2. “Set” as outer type allows for “Set” as inner type only:

   let test_sa: Set<Array<Int>> =
       // compile time error “Type 'Array<Int>' does not conform to
       // protocol 'Hashable'”

   let test_ss: Set<Set<Int>> =
       // ok

   let test_sd: Set<Dictionary<Int, Int>> =
       // compile time error “Type 'Dictionary<Int, Int>' does not
       // conform to protocol 'Hashable'”

A.3. The same is true for “Dictionary” as outer type:

   let test_da: Dictionary<Array<Int>, Int> = [:]
       // compile time error “Type 'Array<Int>' does not conform to
       // protocol 'Hashable'”

   let test_ds: Dictionary<Set<Int>, Int> = [:]
       // ok

   let test_dd: Dictionary<Dictionary<Int, Int>, Int> = [:]
       // compile time error “Type 'Dictionary<Int, Int>' does not
       // conform to protocol 'Hashable'”

B. When letting Swift infer the type of collections of “Array” from
  literals another inconsistency comes to light:

B.1. “Array” as outer type behaves IMHO perfectly:

   var testArray = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
   print(testArray.dynamicType)
       // prints “Array<Array<Int>>”
   testArray.append( [ 1, "five", 25, 625 ] );
       // compile time error “Cannot convert value of 'String' to
       // expected element type 'Int'”; type safe

B.2. “Set” as outer type works but there is no type safety:

   var testSet: Set = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
   print(testSet.dynamicType)
       // prints “Set<NSArray>”
   testSet.insert( [ 1, "five", 25, 625 ] )
       // neither run time nor compile time errors; no type safety

B.3. The same goes for “Dictionary” as outer type:

   var testDictionary = [
       [ 1, 2, 4, 8 ]: "Powers of Two",
       [ 1, 3, 9, 27 ]: "Powers of Three",
   ]
   print(testDictionary.dynamicType)
       // prints "Dictionary<NSArray, String>"
   testDictionary[ [ 1, "five", 25, 625 ] ] = "Powers of Five"
       // neither run time nor compile time errors; no type safety

— — - Wolfgang H.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

6

Inconsistency A. is that “Set” currently is the only collection type conforming to protocol 'Hashable'”. IMHO both “Array” and “Dictionary” should conform to protocol “Hashable”, too.

Set is the only Hashable* collection type because it's the only collection type where all of its values are always Hashable themselves. Array<Element> can be an array of a non-Hashable type; Dictionary<Key: Value> can have a non-Hashable type for Value. If/when Swift gains conditional protocol compliance, arrays and dictionaries of Hashable types could themselves be Hashable, but not until then.

Inconsistency B. is that “Array<Int>” is typesafe if used as element of an “Array” but is non-typesafe if used as element of “Set” or “Dictionary”. The non-typesafety may result from the mapping of “Array<Int>” to “NSArray“.

Since Array<Element> isn't Hashable, you can't create a Set<Array<Int>>. The type system therefore falls back to using the bridged Objective-C type for Array<Int>, which can provide a hash value based on object identity.

Nate

*For my spell checker's sake, could we rename Hashable to Washable? Thanks

···

On Apr 29, 2016, at 1:57 PM, Wolfgang H. via swift-evolution <swift-evolution@swift.org> wrote:

- - - Wolfgang H.

Am 2016-04-29 17/Fr um 20:18 schrieb Xiaodi Wu - xiaodi.wu@gmail.com:

I'm not sure I understand the inconsistency you see. Set and Dictionary require hashable values and keys, respectively. That's just in the nature of what these types are. Do you want Set itself to conform to Hashable?

On Fri, Apr 29, 2016 at 12:57 Wolfgang H. via swift-evolution <swift-evolution@swift.org> wrote:

A. When trying to declare nested collection types an inconsistency
is unveiled:

A.1. “Array” as outer type allows for every collection type as inner
   type (“Int” used as a placeholder for “some other type”):

  let test_aa: Array<Array<Int>> =
      // ok

  let test_as: Array<Set<Int>> =
      // ok

  let test_ad: Array<Dictionary<Int, Int>> =
      // ok

A.2. “Set” as outer type allows for “Set” as inner type only:

  let test_sa: Set<Array<Int>> =
      // compile time error “Type 'Array<Int>' does not conform to
      // protocol 'Hashable'”

  let test_ss: Set<Set<Int>> =
      // ok

  let test_sd: Set<Dictionary<Int, Int>> =
      // compile time error “Type 'Dictionary<Int, Int>' does not
      // conform to protocol 'Hashable'”

A.3. The same is true for “Dictionary” as outer type:

  let test_da: Dictionary<Array<Int>, Int> = [:]
      // compile time error “Type 'Array<Int>' does not conform to
      // protocol 'Hashable'”

  let test_ds: Dictionary<Set<Int>, Int> = [:]
      // ok

  let test_dd: Dictionary<Dictionary<Int, Int>, Int> = [:]
      // compile time error “Type 'Dictionary<Int, Int>' does not
      // conform to protocol 'Hashable'”

B. When letting Swift infer the type of collections of “Array” from
literals another inconsistency comes to light:

B.1. “Array” as outer type behaves IMHO perfectly:

  var testArray = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
  print(testArray.dynamicType)
      // prints “Array<Array<Int>>”
  testArray.append( [ 1, "five", 25, 625 ] );
      // compile time error “Cannot convert value of 'String' to
      // expected element type 'Int'”; type safe

B.2. “Set” as outer type works but there is no type safety:

  var testSet: Set = [ [ 1, 2, 4, 8 ], [ 1, 3, 9, 27 ] ]
  print(testSet.dynamicType)
      // prints “Set<NSArray>”
  testSet.insert( [ 1, "five", 25, 625 ] )
      // neither run time nor compile time errors; no type safety

B.3. The same goes for “Dictionary” as outer type:

  var testDictionary = [
      [ 1, 2, 4, 8 ]: "Powers of Two",
      [ 1, 3, 9, 27 ]: "Powers of Three",
  ]
  print(testDictionary.dynamicType)
      // prints "Dictionary<NSArray, String>"
  testDictionary[ [ 1, "five", 25, 625 ] ] = "Powers of Five"
      // neither run time nor compile time errors; no type safety

— — - Wolfgang H.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

7

Well put, Nate.
It will be a great day when conditional protocol compliance comes to Swift.
Until then, there's good reason why Array and Dictionary can't be washed.

···

On Fri, Apr 29, 2016 at 2:49 PM, Nate Cook via swift-evolution < swift-evolution@swift.org> wrote:

> On Apr 29, 2016, at 1:57 PM, Wolfgang H. via swift-evolution < > swift-evolution@swift.org> wrote:
>
> Inconsistency A. is that “Set” currently is the only collection type
conforming to protocol 'Hashable'”. IMHO both “Array” and “Dictionary”
should conform to protocol “Hashable”, too.

Set is the only Hashable* collection type because it's the only collection
type where all of its values are always Hashable themselves. Array<Element>
can be an array of a non-Hashable type; Dictionary<Key: Value> can have a
non-Hashable type for Value. If/when Swift gains conditional protocol
compliance, arrays and dictionaries of Hashable types could themselves be
Hashable, but not until then.

> Inconsistency B. is that “Array<Int>” is typesafe if used as element of
an “Array” but is non-typesafe if used as element of “Set” or “Dictionary”.
The non-typesafety may result from the mapping of “Array<Int>” to “NSArray“.

Since Array<Element> isn't Hashable, you can't create a Set<Array<Int>>.
The type system therefore falls back to using the bridged Objective-C type
for Array<Int>, which can provide a hash value based on object identity.

Nate

*For my spell checker's sake, could we rename Hashable to Washable? Thanks