[Pitch] Conditionally conform Optional: Sequence where Wrapped: Sequence

Sequence is a particularly important protocol, because it governs which types can be iterated in a for loop. To this end, I think it is worthwhile to make Optional conform to Sequence when its wrapped value conforms to Sequence.

In general, I don't like the idea of the language dictating default behavior, because the default semantics might not be universally desirable. In this case, however, I think this has very universal, obvious semantics:

  • If there is something to iterate: iterate it
  • If there is nothing to iterate: don't iterate it

Here's a sample implementation:

public extension Optional: Sequence where Wrapped: Sequence {
	public typealias Element = Wrapped.Iterator.Element
	public typealias Iterator = AnyIterator<Wrapped.Iterator.Element>

	public func makeIterator() -> AnyIterator<Wrapped.Iterator.Element> {
		return self.map { AnyIterator($0.makeIterator()) }
			?? AnyIterator(EmptyCollection().makeIterator())
	}
}

Usage:

let a: [Int]? = [1, 2, 3]
for i in a {
    print(a)
}

I found this particularly useful when you wish to do something for every element in a sequence returned by a throwing method. Compare the before/after:

func throwingFunc() -> [1, 2, 3] { return [1, 2, 3] }

// before:
let result = try? throwingFunc()
if let result = result {
    for element in result {
        print(result)
    }
}

// after:
for element in try? throwingFunc() {
    print(element)
}

Now, you might be thinking, "just use the nil coalescing operator to default to an empty collection ([] or "")!" And this is possible, for Array, Set, Dictionary, String. But what about other sequence/collection types? How do you make an empty UnfoldSequence<Int, (Int, Int)>? sequence(state: (0, 0), next: { _ in nil })? Yikes!

2 Likes

Another one that make sense to add, when SE-0134 is implemented, is Hashable, so that we can have Sets and Dictionary(s) of Optionals:

extension Optional: Hashable where Wrapped: Hashable {
	var hashValue: Int {
		return self?.hashValue ?? 0
	}
}

I'm sure there are more, which makes me wonder: is something like this scalable? Will we end up with a hundred different extensions to Optional for each protocol which has a "default" for Optional?

Why is nil 0, what about hashes that have 0 as a valid hash value?

Oh yes! I forgot about this! I literally had to implement my own HashableOptional type. It lacked all the language support (if let, ?? ?., !), so I ended up having to bridge back and forth. Very frustrating!

Also would you consider optionals where Wrapped are different types to say that there nil’s are equal?

what about hashes that have 0 as a valid hash value?

This is fine; hash values don't have to be unique, so it's possible that nil overlaps with something else.

3 Likes

What the hash value of nil is could be determined later, but you'll always be susceptible to a collision. Any value of integer is a possible hash value (in theory). You need to reserve a value for nil one way or another. Perhaps 0 is a bad choice though, it's probably much more likely than other numbers.

It would be pretty easy to rig up a debugger to a large project's hashValues, and to do a frequency analysis of hash values. The least frequent one could be used for nil.

Notice that I didn't define an extension for Equatable here. Two values with the same hash aren't necessarily equal.

1 Like

Maybe it is. Is there a way to generalize the concept of Defaultable for protocols like Sequence, Hashable, Dictionary and the (possibly many) others?

EDIT: the idea would be to have these extensions be auto-generated from Optional and the Defaultable protocols, or something equivalent to that.

Yeah, the conditional conformance of Optional to Equatable is already planned.

This is fine; hash values don’t have to be unique

To elaborate for others: hashed collections fall back to using == to distinguish elements when hash values collide.

Bikeshedding, but Defaultable is a bit unclear. But I like the idea. A protocol that your protocol P derives from, in order to:

  • To mark your protocol P for automatic synthesis of extension Optional: P where Wrapped: P
  • Some mechanism to define the behaviors. Idk how this would work. In the general case, this would be boil down to pretty much the same as manually writing the conformance yourself. So I guess the scope would be limited down to where you provide a default instance, and all methods of Optional<P>, in the nil case, would behave as they would on that instance.

:-1: from me on the conditional conformance.

Forwarding to the wrapped value isn't the only way to conform Optional to Sequence. It might be the most obvious, but only by a little. You could also consider an Optional to be a sequence (Collection, even) of 0 or 1 values. See some prior discussions (split across two threads): Revisiting Optionals as Sequences & Revisiting Optionals as Sequences

Furthermore this could produce subtly surprising behavior — imagine you have let x: [[Int]]. In that case Array(x.map { $0 + [] }) is a no-op. If during later refactoring x becomes [[Int]]?, suddenly Array(x.map { $0 + [] }) produces something completely different.

6 Likes

Surely that’s a problem though. Because my understanding was that if two hashValues are the same then the objects must be equal. And now we are going to end up with nil being equal to something else other than nil?

Because my understanding was that if two hashValues are the same then the objects must be equal.

Unfortunately, that's not quite the case. For example, consider UInt64 on systems where Int is 32 bits. hashValue is always an Int, so how would every UInt64 have a different hash value? The only thing a hash value can tell you is if two objects are not equal.

3 Likes

Btw collection of one will receive flatMap, which leads to topic problem resolution: .flatMap { $0 }

Yes, but that isn't of much use. The benefit of being able to use it in a for loop is of dubious value, but I do see value in filter ( equivalent to flatMap { predicate(self) ? self : nil }) or forEach (perform a closure if not nil). However, both of those are possible without Sequence conformance (as map and flatMap currently are).

This is an interesting point.

This is incorrect. Only the converse is true: if the values are equal, the hash values must also be equal.

The reverse cannot be true. Consider that hashValue is an Int. How many possible hash values are there? Now consider a hashable and equatable [Int]. How many possible distinct arrays of int are there? Far more. (Number of ints raised to the power of the max array size, to be precise.) That means that there must be some arrays of ints that have the same hash value but do not compare equal.

Here is some background reading on hashing: Hash function - Wikipedia

Isn’t this a problem with the name map being duplicated between Optional and Sequence, and not a problem with the proposal at hand?

The main problems I see here are that:

  • as stated, not everyone will agree on the way in which Optional should conform to Sequence
  • some may find it useful to have Optional : Sequence where Wrapped : Sequence in the way outlined in the pitch, but not all will
  • you can only conditionally conform to a protocol once, so someone who might want to use Optional : Sequence where Wrapped == MyType in their own project, with an implementation that makes sense to them, will be barred from doing so if this ships

That last point is key here. As a result, IMO, only the most "obvious" conditional conformances--basically, those that allow replacing existing types (such as CountableRange being replaced with Range where Bound : SignedInteger), or are already partially simulated (such as Array : Equatable where Element : Equatable) should be shipped as conditional conformances that everyone has to abide by.

3 Likes

Ooof yeah, that's a really good point.