Go Pattern Matching

I’ve been playing around with Go Generics a bit since they became available in the 1.18 release. One common feature combo of functional programming languages is the sum type, coupled with pattern matching. Haskell has data and case, Rust has enum and match.

The sum type defines variants of an overall type, and the pattern matching expression executes different code depending on the variant encountered at runtime. The value of pattern matching is that the sum type must be unwrapped to access the values any variant contains and, when unwrapped via a match expression, that compilers force the match expression to handle all possible vairants.

Two common uses are Results and Options. Results are types that represent a possibly failed computation. Options are types that represent the potential absence of a value. For Results, pattern matching means that you must handle the possibility of there being an error if you wish to access the result. For Options, it means that you must handle the potential absence of a value before accessing it. The compiler has your back. In Haskell these are Either and Maybe, in Rust Result and Option.

Go does not have slick built-in syntax for this technique, but it can be simulated with a struct and a handful of package-level functions for each sum type. With generics, common types like Result and Option can be defined once and reused with different value types.

The basic technique is this:

  1. A package for the sum type.
  2. A struct to hold the values.
  3. A function to construct each variant.
  4. A function for pattern-matching.

(1) A new package, so we can name the function Match for every sum type. Further, if the Match function has a generic return type that depends on the code being executed, then it must be package-level, because Go doesn’t support type parameters in methods. There is proposal, though.

(2) The type representing the value doesn’t really have to be a struct, but it must be able to represent which constructor initialized it, so that Match can execute the correct branch.

(3) Each variant is represented by a constructor. Each constructor takes as arguments the values wrapped by that variant. The constructor initializes and returns the struct (2) such that it represents the corresponding variant.

(4) Match takes as arguments the struct (2), and a destructuring function for each possible variant. Each destructuring function takes as arguments the values of that variant. Match detects, based on the internal representation of the struct (2), which variant it is, calls the appropriate destructuring function, and returns the return value of that function. Thanks to type parameters, the return type of Match can be determined at the callsite, rather than in the definition of Match itself. Thanks to Go requiring all defined arguments in any function call, Match enforces handling all variants!

Here are some examples. First, Option, because it’s a bit simpler than Result.

Using Option to resolve defaults for optional configuration values:

type Config struct {
	EnableThing option.Option[bool]
}

type DefaultedConfig struct {
	EnableThing bool
}

func Default(c *Config) *DefaultedConfig {
	return &DefaultedConfig{
		EnableThing: option.Match(c.EnableThing,
			func(v bool) bool { return v },
			func() bool { return true }, // enable by default
		),
	}
}

The definition of Option:

package option

// Option represents the possibility of a value.
// If constructed with Some, it represents a real value.
// If constructed with None, it represents the absence of
// a value.
type Option[T any] struct {
	v *T
}

// Some constructs an Option from a real value.
func Some[T any](v T) Option[T] {
	return Option[T]{&v}
}

// None constructs an Option that represents the absence
// of a value.
func None[T any]() Option[T] {
	return Option[T]{nil}
}

// Match unpacks the Option o and executes some if the Option
// was constructed with Some or executes none if the Option
// was constructed with None. The return value of whichever
// function executes will be returned from Match.
func Match[T, U any](
	o Option[T],
	some func(T) U,
	none func() U,
) U {
	if o.v == nil {
		return none()
	}
	return some(*o.v)
}

Using Result to handle possible error values:

type Cat struct{}
type Dog struct{}
type Thing struct{}

func IsCat(v any) Result[bool] {
	switch v.(type) {
	case Cat:
		return result.Ok(true)
	case Dog:
		return result.Ok(false)
	default:
		return result.Error[bool](errors.New("couldn't tell"))
	}
}

// This example ignores the return value from Match, which
// is why we just return the empty struct. This is a bit
// verbose but is required to satisfy the requirement in
// Match's type that the funcs have a return value.
func main() { // prints "error: couldn't tell"
	v := Thing{}
	result.Match(IsCat(v),
		func(isCat bool) struct{} {
			if isCat {
				fmt.Println("cat!")
			} else {
				fmt.Println("not cat...")
			}
			return struct{}{}
		},
		func(err error) struct{} {
			fmt.Printf("error: %v\n", err)
			return struct{}{}
		})
}

The definition of Result:

package result

import "errors"

// Result represents the result of a computation.
// If constructed with Ok, it represents a success.
// If constructed with Error, it represents a failure.
type Result[T any] struct {
	v   *T
	err error
}

// Ok constructs a result from a value.
func Ok[T any](v T) Result[T] {
	return Result[T]{v: &v}
}

// Error constructs a Result from an error.
func Error[T any](err error) Result[T] {
	if err == nil {
		err = errors.New("")
	}
	return Result[T]{err: err}
}

// Match unpacks the Result r and executes ok if the Result
// was constructed with Ok or executes e if the Result was
// constructed with Error. The return value of whichever
// function executes will be returned from Match.
func Match[T, U any](
	r Result[T],
	ok func(v T) U,
	e func(err error) U,
) U {
	if r.err != nil {
		return e(r.err)
	}
	return ok(*r.v)
}

There are probably ways to optimize the representation, perhaps using Go’s unsafe package to implement tagged unions that reuse memory for each variant, but I haven’t tried yet.

This is not idiomatic Go. It might be slower than the conventional if err != nil due to the use of first-class functions and (potentially) closures. But it is kind of cool. Perhaps it will catch on, perhaps not.

I have been playing with various ideas in my go-types repo.

May 15, 2022