Proposal: SetProtocol

Proposal.md

Adding the SetProtocol Protocol to Swift

• Proposal: SE-TBD
• Author(s): Dave DeLong
• Review manager: TBD
• Status: TBD

Introduction

A new public protocol named SetProtocol unifies set semantics.

This proposal was discussed on-forum in the TBD thread.

Motivation

A major source of "why doesn't this just work?" frustration rises from the turbulent edge of Cocoa and Swift. Consider the disparity between CharacterSet and Set<Character>. The former, bridged from Foundation, is a set of Unicode.Scalar values. The latter is an actual Set of extended grapheme clusters.

Being a struct, Set<T> cannot perform simple set-like operations. It cannot be inverted like a CharacterSet. This is a common operation to perform when parsing a string, for example. Given a CharacterSet that describes allowed characters, the inversion describes disallowed characters.

let newlines = CharacterSet.newlines
let charactersThatAreNotNewlines = newlines.inverted

Set<T> is a Collection. Inverting it is impossible. Set<Character> cannot know the entire domain of Character values over which it should iterate.

Inverting CharacterSet over a Swift type is also impractical. It is limited to Unicode.Scalar values and cannot, for example, contain emoji. Most emoji are composed of multiple Unicode.Scalar values.

Swift needs a way to describe an abstract set, which can test containment but does not promise iteration support.

Detailed Design

public protocol SetProtocol {
    associatedtype Element
    
    /// Returns a truth value indicating whether an element is a
    /// member of a conforming instance
    func contains(_ element: Element) -> Bool
    
    /// Returns an instance of `Self` over the associated type domain, 
    /// with the current elements removed.
    var inverted: Self { get }
    
    /// Returns a union of two instances of the conforming type
    func union<S: SetProtocol>(_ other: S) -> Self where S.Element == Element
    
    /// Returns the intersection (possibly empty) of two instances
    /// of the conforming type
    func intersect<S: SetProtocol>(_ other: S) -> Self where S.Element == Element
    
    /// Returns `self`, removing any items that appear in the union of
    /// `self` and `other`
    func subtracting<S: SetProtocol>(_ other: S) -> Self where S.Element == Element
    
    /// Returns the union of items unique to `self` and `other`
    func symmetricDifference<S: SetProtocol>(_ other: S) -> Self where S.Element == Element
    
    /// Updates `self` to the associated type domain, with the current
    /// elements removed
    mutating func invert()
    
    /// Updates `self` by forming a union with `other`
    mutating func formUnion<S: SetProtocol>(_ other: S) where S.Element == Element
    
    /// Updates `self` by removing any members that do not appear
    /// in `other`.
    mutating func formIntersection<S: SetProtocol>(_ other: S) where S.Element == Element
    
    /// Updates `self` by removing any members that appear in `other`.
    mutating func subtract<S: SetProtocol>(_ other: S) where S.Element == Element
    
    /// Updates `self` by removing members that appear in `other` and
    /// adding items that appear in `other` that are not in `self`.
    mutating func formSymmetricDifference<S: SetProtocol>(_ other: S) where S.Element == Element

}

• CharacterSet will conform to SetProtocol with the associatedtype of Unicode.Scalar.
• Set<T> will conform to SetProtocol with the associatedtype of Element, its generic element.
• A new PredicateSet<T> struct will be added. It can type-erase any SetProtocol conformant. Its containment is defined by executing a closure.

Operators

SetProtocol types are naturally usable with operators.

let newlines = CharacterSet.newlines
let charactersThatAreNotNewlines = !newlines
 
let whitespacesAndNewlines = CharacterSet.whitespacesAndNewlines
let whitespaces = whitespacesAndNewlines - newlines

let whitespacesAndDigits = whitespaces + CharacterSet.digits

/// ...and so on

The standard library could provide operators for union (+ and ||), intersection (&&), subtraction (-), symmetric difference (^), and inversion (!).

Source compatibility

This proposal is strictly additive.

Effect on ABI stability

This proposal does not affect ABI stability.

Effect on API resilience

This proposal does not affect ABI resilience.

Alternatives Considered

Not at this time