GoADT

Algebraic data types generator for the Go programming language

Tech stack

• Haskell
• Golang
• Parsec
• CmdArgs
• Go-Sumtypes

Product types

A product type A x B is a compounded type that combines one element from each of the types. According to the Curry-Howard isomorphism, it corresponds to the AND operation in intuitionistic logic.

In golang, we are going to represent product types as structs.

-- haskell
data Tuple a b = Tuple
  { x :: a
  , y :: b
  }

// golang
type Tuple[A, B any] struct {
    x A
    y B
}

Sum types

A sum type A + B is a compounded type that requires one element from one of the types. According to the Curry-Howard isomorphism, it corresponds to the OR operation in intuitionistic logic.

In golang, we are going to represent product types as interfaces

-- haskell
data Either a b
  = Left a
  | Right b

// go
type Either[A, B any] infterface {
    implEither()
}

type Left[A, B any] struct { a A }
func (_ Left) implEither() {}

type Right[A, B any] struct { b B }
func (_ Right) implEither() {}

Using ADTs

Let's start with an example of an ADT: Opt. This type represents the possibility of the non-existence of a value (in Haskell it's known as Maybe, but we will define an isomorphic Opt type)

-- haskell
data Opt a
  = None
  | Some a

// go
type Opt[A any] interface { implOpt() }

// Data Constructors Structs
type Some[A any] struct { V A }
type None[A any] struct {     }

// Implement the interface
func (_ Some[A]) implOpt() { }
func (_ None[A]) implOpt() { }

// Constructors
func NewSome[A any](V A) Opt[A] { return Some[A]{ V: V } }
func NewNone[A any](   ) Opt[A] { return None[A]{      } }

Now, let's see how to use it. In most functional programming languages (like Haskell, Ocaml and SML) ADTs can be used with pattern matching, but, unfortunately, go does not have that feature. The closest analog is a type switch.

-- haskell
map :: (a -> r) -> Opt a -> Opt r
map fn (Some v) = Some $ fn v
map fn  None    = None

// go
func Map[A, R any](fn func(A) R, opt Opt[A]) (res Opt[R]) {
	switch t := opt.(type) {
	case Some[A]: res = NewSome(fn(t.V))
	case None[A]: res = NewNone[R]()
	}
	return
}

If you build your functions this way, go-sumtype can be used to check for the exhaustiveness of the type switches.

Using GoADT

Check the examples directory to see how one could use goadt and go generate to automatically generate ADTs

References:

1. Go and Algebraic data types by Eli Bendersky
2. Sum Types in Go by Jeremy Bowers
3. Golang Tips #1: ADT by Romain Guilmont
4. Alternatives to sum types in Go by Will Sewell
5. Wikipedia's article on ADTs
6. Algebraic Data Types in Haskell by Gints Dreimanis
7. Why algebraic data types are important by Bartosz Milewski
8. go-sumtype an exhaustiveness checker for sum types by Andrew Gallant