How to implement a generic Either type in Go?

Question

With the new generics in Go 1.18, I thought it might be possible to create a 'Either[A,B]' type that can be used to express that something could be either of type A or type B.

A situation where you might use this is in situations where a function might return one of two possible values as a result (e.g. one for 'normal' result and one for an error).

I know the 'idiomatic' Go for errors would be to return both a 'normal' value and an error value, returning a nil for either the error or the value. But... it sort of bothers me that we are essentially saying 'this returns A and B' in the type, where what we really mean to say is 'this returns A or B'.

So I thought maybe we can do better here, and I thought this might also be a good exercise to see/test the boundaries of what we can do with these new generics.

Sadly,try as I might, so far I have not been able solve the exercise and get anything working/compiling. From one of my failed attempts, here is an interface I'd like to implement somehow:

//A value of type `Either[A,B]` holds one value which can be either of type A or type B.
type Either[A any, B any] interface {

    // Call either one of two functions depending on whether the value is an A or B
    // and return the result.
    Switch[R any]( // <=== ERROR: interface methods must have no type parameters
        onA func(a A) R),
        onB func(b B) R),
    ) R
}

Unfortunately, this fails rather quickly because declaring this interface isn't allowed by Go. Apparantly because 'interface methods must have no type parameters'.

How do we work around this restriction? Or is there simply no way to create a 'type' in Go that accurately expresses the idea that 'this thing is/returns either A or B' (as opposed to a tuple of both A and B).

Cud

type Either[A any, B any, R any] . – Brevity

Either[A any, B any, R any] interesting idea, but that seems illogical to me. The type R has nothing todo with expressing the idea that 'the thing we return here is 'either an A or a B' so when make a 'Either A or B' value we'd have to specify also a third irrelevant type which makes no sense really. – Cud

Answer 1

The Either could be modeled as a struct type with one unexported field of type any/interface{}. The type parameters would be used to ensure some degree of compile-time type safety:

type Either[A, B any] struct {
    value any
}

func (e *Either[A,B]) SetA(a A) {
    e.value = a
}

func (e *Either[A,B]) SetB(b B) {
    e.value = b
}

func (e *Either[A,B]) IsA() bool {
    _, ok := e.value.(A)
    return ok
}

func (e *Either[A,B]) IsB() bool {
    _, ok := e.value.(B)
    return ok
}

If Switch has to be declared as a method, it can't be parametrized in R by itself. The additional type parameter must be declared on the type definition, however this might make usage a bit cumbersome because then R must be chosen upon instantiation.

A standalone function seems better — in the same package, to access the unexported field:

func Switch[A,B,R any](e *Either[A,B], onA func(A) R, onB func(B) R) R {
    switch v := e.value.(type) {
        case A:
            return onA(v)
        case B:
            return onB(v)
    }
}

A playground with some code and usage: https://go.dev/play/p/g-NmE4KZVq2

Scallion

Short of union types (i.e. closed type sets) in Go, this is as good an answer as it gets. The question is: is that where we, as a community, want to take Go? I'm a big fan of Haskell, but I'm not sure this style agrees with Go. – Alguire

This solution doesn't work if A=B, such as Either[int, int]. (I assume the idea was to represent a sum type or disjoint union, like Haskell's Either. I would think the way to do that in Go is using polymorphism, along the lines of G4143's answer.) – Fourteenth

@Fourteenth an Either type is supposed to be either some type or some other. If the use case is "exists" vs. "not exists" that's an optional, not an Either. – Scallion

@Scallion In Haskell, Either a b represents the disjoint union of types a and b (ie a sum or coproduct algebraic data type). a and b don't have to be different. If they're the same, Either a a is like two copies of a, a left and a right copy. As far as I know, Either types originated in Haskell. – Fourteenth

@Fourteenth I'm not a Haskell expert, although polymorphism like G4143's answer doesn't actually produce an algebraic data type, because it would be possible to extend it by implementing the interface. You're right that my solution fails for A=B. If Haskell's Either a b admits a=b then this definitely isn't a perfect Go port – Scallion

Answer 2

If I had to do this, I would look up a functional programming language(like OCaml) and knock-off their solution of the either type..

package main

import (
    "errors"
    "fmt"
    "os"
)

type Optional[T any] interface {
    get() (T, error)
}

type None[T any] struct {
}

func (None[T]) get() (T, error) {
    var data T
    return data, errors.New("No data present in None")
}

type Some[T any] struct {
    data T
}

func (s Some[T]) get() (T, error) {
    return s.data, nil
}

func CreateNone[T any]() Optional[T] {
    return None[T]{}
}

func CreateSome[T any](data T) Optional[T] {
    return Some[T]{data}
}

type Either[A, B any] interface {
    is_left() bool
    is_right() bool
    find_left() Optional[A]
    find_right() Optional[B]
}

type Left[A, B any] struct {
    data A
}

func (l Left[A, B]) is_left() bool {
    return true
}

func (l Left[A, B]) is_right() bool {
    return false
}

func left[A, B any](data A) Either[A, B] {
    return Left[A, B]{data}
}

func (l Left[A, B]) find_left() Optional[A] {
    return CreateSome(l.data)
}

func (l Left[A, B]) find_right() Optional[B] {
    return CreateNone[B]()
}

type Right[A, B any] struct {
    data B
}

func (r Right[A, B]) is_left() bool {
    return false
}

func (r Right[A, B]) is_right() bool {
    return true
}

func right[A, B any](data B) Either[A, B] {
    return Right[A, B]{data}
}

func (r Right[A, B]) find_left() Optional[A] {
    return CreateNone[A]()
}

func (r Right[A, B]) find_right() Optional[B] {
    return CreateSome(r.data)
}

func main() {
    var e1 Either[int, string] = left[int, string](4143)
    var e2 Either[int, string] = right[int, string]("G4143")
    fmt.Println(e1)
    fmt.Println(e2)
    if e1.is_left() {
        if l, err := e1.find_left().get(); err == nil {
            fmt.Printf("The int is: %d\n", l)
        } else {
            fmt.Fprintln(os.Stderr, err)
        }
    }
    if e2.is_right() {
        if r, err := e2.find_right().get(); err == nil {
            fmt.Printf("The string is: %s\n", r)
        } else {
            fmt.Fprintln(os.Stderr, err)
        }
    }
}

Kerr

One thing is that most of your functions and methods are unexported; therefore, the type is basically unusable outside the package where it's declared. Another thing is that the Optional interface and its two implementors Some and None do not form an algebraic data type (or a closed union, if you prefer that term): anyone could create another struct type that implement Optional simply by embedding an Optional in the struct. Sadly, you cannot just transpose how it's done in OCaml, Haskell, etc. to Go. – Alguire

@juBObs,About the visibility of the functions. Its an example where everything is in the main package for simplicity. About your complaint that anyone could create another struct type that could implement Optional..That basically a complaint of the language. – Kerr

Well, yes. The Go language doesn't provide a good way of doing what you want to do. – Alguire

Answer 3

You can use the https://github.com/samber/mo library (disclaimer: I'm the project author).

Either signature is:

type Either[L any, R any] struct {}

Some examples:

import "github.com/samber/mo"

left := lo.Left[string, int]("hello")

left.LeftOrElse("world")
// hello

left.RightOrElse(1234)
// 1234

left.IsLeft()
// true

left.IsRight()
// false

Your question about a Switch pattern can be implemented this way:

import "github.com/samber/mo"

left := lo.Left[string, int]("hello")

result := left.Match(
    func(s string) Either[string, int] {
        // <-- should enter here
        return lo.Right[string, int](1234)
    },
    func(i int) Either[string, int] {
        // <-- should not enter here
        return lo.Right[string, int](i * 42)
    },
)

result.LeftOrElse("world")
// world

result.RightOrElse(42)
// 1234

Footlight

Answer 4

A solution finally came to me. The key was defining the 'Either' type as a 'struct' instead of an interface.

type Either[A any, B any] struct {
    isA bool
    a   A
    b   B
}

func Switch[A any, B any, R any](either Either[A, B],
    onA func(a A) R,
    onB func(b B) R,
) R {
    if either.isA {
        return onA(either.a)
    } else {
        return onB(either.b)
    }
}

func MakeA[A any, B any](a A) Either[A, B] {
    var result Either[A, B]
    result.isA = true
    result.a = a
    return result
}

func MakeB[A any, B any](b B) Either[A, B] {
  ... similar to MakeA...
}

That works, but at the 'price' of really still using a 'tuple-like' implementation under the hood were we store both an A and a B but ensure it is only possible to use one of them via the public API.

I suspect this is the best we can do given the restrictions Go puts on us.

If someone has a 'workaround' that doesn't essentially use 'tuples' to represent 'unions'. I would consider that a better answer.

Cud

Storing a bool to differentiate the types seems redundant. – Arsonist

Then how would you you choose which of the two functions to call? – Cud

Trying to understand the larger use case. If I'm understanding your original question, is it to just just one value - an error or a result? if so, I'd hinge my logic on if the returned type satisfies the error interface or not. – Arsonist

The 'error' example was just give an idea why you might want to do something like this, but I was looking for something that can express 'either A or B' more generally. For example, 'this function returns either a number or a string' Either[int,string]. – Cud

Practically speaking, I think what you probably would do in real-world cases that need something like 'Either[int,string]' would be to just define it as returning any and use type switch to work with the value. But unless the two different types of things you are returning share some common interface that characterizes them both, go doesn't seem to offer any way to really say that your function 'can return either this or that'. That kind of precision just doesn't seem possible in go's type system. If go was 'English' it's like they have a word for 'and' but forgot to add a word for 'or' – Cud