Adding Either type to the Standard Library

I’m assuming you are talking about Union Tuples - not regular ones.

I don’t think it would. Up-thread there has been a lot of discussion about an OneOf type. Or how multiple such types (OneOf2, OneOf3...) could be added. I think the “multiple such types” post will give you an ideas of how we could migrate to a variadic OneOf. To sum it up, we would just deprecate Either and encourage the use of OneOf in its place. So if you’re concerned that Either will limit our future options, you shouldn’t.

Compiler magic to convert the expression:

typealias MyOneOf 
    = (foo: Foo | bar: Bar)

Could be converted to:

typealias MyOneOf(first|second|) 
    = OneOf<Foo, Bar>

That would be similar to another post that proposes baking the closure labels into the identifier. That though is a future proposal altogether, that requires to be built one top of OneOf. There has also been talk of a “native” Union Tuple type, that will have custom compiler support. Nonetheless, that type is not acceptable to the Core Team, as they are hardly keen on the idea of an OneOf a type that is currently unimplementable as it requires advanced variadic genetics - correct me if I’ve misinterpreted. All in all, I would appreciate ideas that are applicable to the proposal of adding an Either like type. Lastly, I’d like to say that I don’t see a Union Type built into the compiler as a reasonable option, because it would further complicate the compiler and because there has been talk of even replacing Tuples with a normal type.

I don’t believe union tuple is a common term.

I’m talking about the comparison between tuples and structs, vs either/anyof and enum.

The tuple (Double, Double) isn’t nearly as useful as a labeled (x:,y:), (r:, angle:), (width:, height:), etc. Either<String, Int> fails to allow for capturing what the semantics actually are - a string or int of what? When is the value one vs the other?

A tuple has clear limitations where it does not support encapsulation or polymorphism - you cannot have a tuple implement a protocol or add additional methods. You can do both of these with an Either type. This creates tension in that people can leverage an either/anyof type long after they should have moved to enum (perhaps because moving from either to enum is a breaking change). Examples of changes might be adding properties to give ‘friendly names’ to left/right, implementing protocols like Comparable, etc.

3 Likes

I think @Dmitriy_Ignatyev lays out pretty compelling reasons for Either's addition:

I feel like a need to clarify that Either won't try to replace all 2-case enums and neither will OneOf replace all enums, just as Tuples haven't replaced structs. Tuples still have labels and they are more concise, still though structs are usually preferred. Either just as Tuples, fits naturally in places where the creation of a new type just doesn't make sense. For example, such a type is present in the Standard Library, in the "automatic protocol satisfaction" proposal, in function builders it would make sense if it was used instead of two separate - and confusing - buildEither methods. Additionally, in places where the creation of a new type is currently not allowed:

struct FooGeneric {
    func fooGeneric<Baz>(baz: Baz) {
        enum State { case bar(Bar), case foo(Foo) } // ❌ 

        ...
    }
}

of course we can do:

struct FooGeneric {
    enum State { case bar(Bar), case foo(Foo) }

    func fooGeneric<Baz>(baz: Baz) {
        ...
    }
}

but in the above cases if we use State just in fooGeneric it would make much more sense for an Either type to take State's place. Not to mention the boilerplate that would be required should we want Equatable conformance.

I recognise that Either is not the ideal type, we'd all like to have. Nonetheless, I feel that it is needed for the cases outlined above - or at least it would make them more pleasant to deal with. Finally, let's not forget that having an OneOf as I mentioned before, is not an option currently, so adding Either for now seems like a good option and discussing how to best implement is the goal of this discussion. If you have any other ideas that are realistic for the above examples and is more elegant than Either feel free to share them.

1 Like

One important thing to keep in mind is that there is really no adding something to the standard library "for now". If something is added to the standard library, then it will be there for a very long time unless the Swift team is willing to break source and/or binary-compatibility to remove it.

Thus, additions to the standard library should meet a very high bar, and any such proposal should explain why it is critical that it be added now instead of focusing those efforts on building up the lower-level foundations of the language like variadic generics and constructing some way of expressing variadic cases so that something better could be provided, since—by your own post above—"Either is not the ideal type".

7 Likes

This is why I am opposed to introducing Either and why I think it is appropriate to discuss things like structural sum types in this thread.

4 Likes

First of all, I’d like to address the part regarding focusing our efforts on variadic generics. I think everyone wants variadic generics, especially me. I’ve been working with function builders and without variadic generics some parts are really mess. But I hate to see, that discussion about variadic generics has been going on for years, yet still to this date there’s no such feature. Not to mention that an OneOf type would require probably an advanced Variadics feature, as repetition of an element - OneOf<Foo, Foo> - should not be allowed.

What has been presented in this thread are real problems - in my previous post I think I mentioned some. So, seeing function builders, the standard library and other projects result to custom types and more repetitive code - that in most cases are just boilerplate - I though that a sensible direction would be a standardized Either type. And many counter-proposals I don’t see a viable alternative. What Either offers is a great set of features - custom conformance, a standardized type etc.

Yes I still think Either isn’t ideal overall, but it’s best for now, where there is a need for such a type. Furthermore, if a new Variadic type comes along and renders the use of a two-case Either type useless, it could slowly be deprecated and removed.

To sum up, there are problems that require an Either like type, whether it’ll be named Either or OneOf doesn’t matter, what matters is that those problems be solved. Once an OneOf comes along, which will most likely take a while, Either will have already helped in a lot of situations and eliminated a lot of boilerplate.

None of that, IMO, is a reason to rush a feature that we already know will incur technical debt in the standard library the minute it lands. Instead, the fact that variadic generics keep coming up in discussions across numerous proposed features and that people want to try to work around the lack of them in different ways is a sign that variadic generics needs to be a much higher priority than it is today, so that other parts of the language can move forward more easily.

16 Likes

What? Why not?

When I refer to a OneOf type, I mean I mean a Variadic option type:

typealias MyType = OneOf<A, B, C>

to use MyType:

let myType = MyType(choosing: A())

To answer your question, I guess OneOf could allow that by requiring an index in its initialisation, but there are substantial drawbacks to doing that:

  1. A Tuple - (Foo, Foo) or just Foo - would be the correct way to do that.
  2. Features like "myType as? A", "MyType(choosing: A())" would not be able to be added in the future without source-breaking changes.
  3. It would be slower to do so - with run-time checks, and without compiler-errors it could be frustrating to get run-time ones.

(Foo, Foo) is not the correct way to model a tagged union of Foo and Foo. (Bool, Foo) can model it.

I don't necessarily think myType as? A is a good idea, but it's not clear to me why it's precluded (or slowed) by allowing OneOf<A, A>. Regarding MyType(choosing:), we already have an extremely similar situation in Combine's Result.Publisher. When the Output and Failure types are different, it just works:

  1> import Combine
  2> struct E: Error { }
  3> Result<Int, Error>.Publisher(E())
$R0: Result<Int, Error>.Publisher = {}

When the Output and Failure types are identical, the ambiguity causes a compile error:

  4> Result<Error, Error>.Publisher(E())
error: repl.swift:4:1: error: ambiguous use of 'init(_:)'
Result<Error, Error>.Publisher(E())
^

Combine.Result:9:16: note: found this candidate
        public init(_ output: Result<Success, Failure>.Publisher.Output)
               ^

Combine.Result:10:16: note: found this candidate
        public init(_ failure: Failure)
               ^

It's fine as long as there's some way to remove the ambiguity. In the Combine case, here's one way:

  4> Result<Error, Error>.Publisher(.success(E()))
$R1: Result<Error, Error>.Publisher = {}

Can somebody please explain, is there any reasons against making current _Either<Left, Right> public instead of internal?
In reality, developers create their own Either type. So, why can't we allow them to use native one, making it public?
I understand that there are some reasons, but it is interesting to know which one.

See my comments above. Something that's purely internal can change or be removed from the standard library; there's no requirement to maintain compatibility with it. But once it's made public and people start using it, it must be maintained potentially indefinitely, even if it's marked deprecated, or until the Swift team decides they're willing to break old code.

Adding public APIs to the standard library is not just about making things convenient for end users—it's a decision that has much longer term consequences for Swift's evolution.

Thanks for your answer. Yes, I keep that in mind. What I mean is that variadic generics and OneOf is an additive feature. Either<A, B> and OneOf(A | B) are not mutually exclusive, we can use both. Am I right, or not?

I don't want to say which of them is better. What I want to say, is that Either<A, B> is useful by itself. And its implementation is one line of code, just Either<A, B>.
To be more precise, the questions are:
Will Either type bring some troubles to implementing OneOf in the future?
Will any conflicts be having them both?

1 Like

I don't think I follow. What I say in my post is that Either<Foo, Foo> is not - logically - valid, as it provides an option between choosing one of two possible types, which are the same. In other words, it's like choosing one of 1 and 1; they're the same. So, if one wants to choose between two values of the same type - Foo in this case - they use a variable. The reason why I included the tuple type: (Foo, Foo) is because someone could have meant to write a tuple instead of a union tuple: (Foo | Foo).

As for the technical aspect, I don't understand how your type could be implemented. I've written a possible implementation of an OneOf type. Could you please show me how it could fit in to such a model or share an implementation of your own?

I thought you were talking about the Either type as described in your original post, but renamed OneOf. That Either type is a tagged union (also called a discriminated union, a sum type, a coproduct, the list goes on…) and allows both type arguments to be the same type.

But now it sounds like you are arguing for untagged unions, not tagged unions. In that case, I agree that OneOf<Foo, Foo> is isomorphic to Foo. But also in that case, IMHO you haven't met the “new information” requirement of the commonly rejected changes list.

As for “how your type could be implemented”, I'm not sure what “your type” refers to. If you mean OneOf<Foo, Foo>, then I was operating under the assumption that OneOf<Foo, Foo> is exactly the Either type of your original post (renamed from Either to OneOf). That Either definition is already supported by the language, so no new implementation is needed.

If you are asking how to model that Either<Foo, Foo> as (Bool, Foo), then this is a 1-1 mapping:

extension OneOf where First == Foo, Second == Foo {
    init(_ tuple: (Bool, Foo)) {
        if tuple.0 { self = .second(tuple.1) }
        else { self = .first(tuple.1) }
    }

    var asTuple: (Bool, Foo) {
        switch self {
        case .first(let f): return (false, f)
        case .second(let f): return (true, f)
        }
    }
}

I still don't get why a tuple is different. When I mentioned (Foo, Foo) as an alternative to Either<Foo, Foo>, I think the user would want to use something like this:

typealias Data = (componentA: Int, componentB: Int)
let data = (componentA: 5, componentB: 6)

But I fail to see how OneOf<Foo, Foo> would be useful - with the extension you wrote. Let's say I want to choose between a state where the user either passed a test and to show their score or they didn't with their mistakes:

typealias TestResult = Either<Score, Mistakes>

let passedTestResult: TestResult = .choosing(Score(10))
let failedTestResult: TestResult = .choosing([
     Mistake.wrongAnswer(5),
     Mistake.wrongAnswer(3)
])

Whereas when I have just scores, what's the point of using Either a not just the bare type Score:

typealias OneOfScores = Either<Score, Score>

let oneOfScores: TestResult = .first(Score(10))

Why not just use a value of type Score:

let score: Score = 10 //or 
                    9 // or whatever value

Your sum type Either<Score, Mistakes> provides an extra bit of information (pass/fail) by virtue of being a tagged union. The sum type Either<Score, Score> also provides that extra pass/fail bit. If you don't provide that bit, and you just give me a bare Score, how can I tell if I passed or failed?

Thanks for the explanation, I get it. It would be useful in the hypothetical OneOf type too. For example, (if labels are added as sugar - let’s not focus on the implementation part):

typealias MyOneOf = (
    passed: Void | 
    failed: Void | 
    wasAbsent: Void
)

One thing we should decide is whether this is worth the trade-offs. For example in the above context initializing OneOf with Void is ambiguous. So what would we do, .passed? Will such a feature be allowed in an unlabeled OneOf type, which will likely be the first to appear?

Still, though, in an Either<Foo, Foo> type would be of limited usefulness. If given the choice I think it’d be better if we gave an error in the same-type Either example, that would prompt the user to switch to a tuple (Foo, Bool).

As I have mentioned several times upthread, one of the primary places structural sums arise is in composition. When they arise under this condition, replacing the sum type with a tuple is not an option. The sum type representation is necessary in some circumstances.

Even when it isn’t, it would be a bad idea to prevent people from using the sum type representation. Nowhere else in the language do we arbitrarily prevent people from using an otherwise valid type.

4 Likes

It's not possible to give an error today (at least not a clear one, I'm not sure if there's something you could hack together to make the compiler reject it) because you would need negative type constraints: enum Either<First, Second> where First != Second. If you want this, now the very simple Either type you're advocating for starts requiring complex new features added to the type checker.

And even then, it's a bad idea to apply that restriction because you're only considering the case of someone writing literally Either<Foo, Foo> in their source code—which is still fine if someone wants to do it, IMO, because two values of the same types can have different semantics which is what the cases capture—but you could also end up with the same type through generic substitution and associated type resolution where it isn't obvious in the source code:

extension Collection {
  subscript(indexOrOffset indexOrOffset: Either<Index, Int>) -> Element {
    ...
  }
}

let array = ["foo", "bar", "baz"]
let element = array[indexOrOffset: /* some value */]
// ^^^ Array.Index == Int,
//     so this argument is Either<Int, Int> and it's perfectly valid

So either you'd have to arbitrarily ban the subscript above as well, or construct your Either type such that it forbids the types to be the same when they're written literally at the type declaration site but let people get around it using generics—neither of these makes sense.

9 Likes