base

README

Base

Base implements Go analogs of the Haskell prelude or base package.

Wat?!

The addition of generics in Go 1.18 opened up the possibility of implementing higher level programming constructs. This library started as an attempt to find out just how far it could "go".

In some way this enterprise was doomed from the start. Haskell has a highly expressive type system bedazzled with the standard trappings of ML inspired languages... Go. Does. Not. Success was not anticipated.

This isn't going to magically turn Go into Haskell (Gaskell?). But if it can implement even a small part of the Haskell prelude that would be pretty swell. Possibly some new tricks could be learned along the way (and maybe some things not to do as well). And those felt like good enough reasons to try.

Besides, it will be such fun!

Design

Cthulhu greets you at a gate of the cyclopean city...

Sum Types

Haskell data is represented using a combination of type structs, interfaces, and receivers. It relies on a trick involving an interface with an un-exported method.

For example, given this definition for Maybe:

data Maybe a = Just a | Nothing

The following simulates the general idea:

type Maybe[A any] interface {
  isMaybe()
}

type Just[A any] struct {
  Value A
}

func (j Just[A])isMaybe() {}

type Nothing struct{}

func (n Nothing)isMaybe() {}

Because isMaybe() is not exported only this package can satisfy it effectively creating a closed set from the normally open set that interfaces provide. Only the types Just[A] and Nothing in this package satisfy the interface and this fact could be used to exhaustively check the different constructors with a switch statement.

This pattern is hinted at in the faq and concrete examples are found in the Go source code for the ast package. I found Jerf's blog entry on sum types to be enlightening. It is common enough that a linter exists go-sumtype.

This setup is however not sufficient to ensure everything is well typed. Consider this:

fmt.Println(Maybe[int](Just[float32]{3}))

We would want the compiler to complain that this is invalid, but as far as the compiler is concerned there's no constraint on the implementation of Maybe[A] being violated and it thinks everything is just awesome.

If we want to ensure that the type parameter is bound and required to match we need to add it to isMaybe():

type Maybe[A any] interface {
  isMaybe(A)
}

This also means we have to add the type paramter to Nothing which isn't exactly a perfect match with the Haskell equivalent, but is better than not having the type checking.

The full solution looks like:

type Maybe[A any] interface {
	isMaybe(A)
}

type Just[A any] struct {
	Value A
}

func (j Just[A]) isMaybe(_ A) {}

type Nothing[A any] struct{}

func (n Nothing[A]) isMaybe(_ A) {}

This now properly rejects the type mismatch:

fmt.Println(Maybe[int](Just[float32]{3}))

./prog.go:22:25: cannot convert Just[float32]{…} (value of type Just[float32]) to type Maybe[int]:
	Just[float32] does not implement Maybe[int] (wrong type for isMaybe method)
		have isMaybe(_ float32)
		want isMaybe(int)

Go build failed.

---

Documentation

Overview

Package base implements Go analogs of the Haskell prelude or base package.