Go言語にジェネリクスが入りそうなのでモナドを作って遊んでみた

この記事は [Applibot Advent Calendar 2021](https://qiita.com/advent-calendar/2021/applibot) 14日目の記事です。
前日は @naotoritty さんの「[Goでのベンチマークツールを作ろうとした話](https://qiita.com/naotoritty/items/3766d2d1aeef7fd17904)」という記事でした。

# はじめに

こんにちは。 (株)Applibotに勤める**型理論信者**エンジニアです。
現在、Goにジェネリクスを導入する動きが進んでいます。
ジェネリクスが入ることでGoは**「ダックタイピングなインタフェース」と「ジェネリクス」を持つ言語**になります。
静的型付けの言語としてはなかなか面白い特徴だと思ったので、モナドを題材にしてこれらがどのように機能するか試してみることにしました。

※この記事は「モナド」と「ジェネリクス(パラメータ多相)」を理解している方向けです

## Goのジェネリクス

はじめに、Goに導入されるであろうジェネリクスについてざっくりと触れておきます。
Go の未来のバージョン(2021/12/14現在)で導入される機能。
面倒な環境構築をしなくても、[このサイト](https://gotipplay.golang.org/)で試すことができます。

```go:遊んでみた例
package main
import "fmt"

type Collection[T any] interface{
	Foreach(f func(T))
}

type Slice[T any] []T

func (s Slice[T]) Foreach(f func(T)) {
	for _, v := range s {
		f(v)
	}
}

func PrintAll[T any](c Collection[T]) {
	c.Foreach(func(value T) {
		fmt.Println(value)
	})
}

func main() {
	slice := Slice[int]{1, 2, 3}
	PrintAll[int](slice)
}
```

構文とできることは次の通りです。

- 型引数は `[` 〜 `]` の中に定義する
- 関数と型に型引数をつけることができる (型は struct、interface、defined type 全てに使える)
- 型に制約をつけることができる
- メソッドに型引数をつけられない (型引数を持つ型にメソッドを定義できるが、メソッドに追加の型引数を定義できない)
- 共変性/反変性がない
- 型引数を高カインド型にできない
- 型推論によって型引数を省略できる

# Goでモナドを定義してみる

まずはジェネリクスの使用感をチェックしつつ、モナドとして扱える型やモナド演算子をいくつか定義します。

## Slice

Go の slice にモナド演算子を定義しました。 `Unit` のほうは `Return` と表記されることもありますが Go においてはキーワードの `return` と紛らわしいので `Unit` にします。

```go:定義
package slice

func Unit[T any](value T) []T {
	return []T{value}
}

func Bind[T, U any](src []T, f func(T) []U) []U {
	var result []U
	for _, v := range src {
		result = append(result, f(v)...)
	}
	return result
}
```

## Option

Optional や Maybe と表記されることもあります。
「値がある」「値がない」という2つの状態をとる型です。

```go:定義
package option

type Option[T any] struct {
	hasValue bool
	value    T
}

func (o Option[T]) Value() (T, bool) {
	return o.value, o.hasValue
}

func Some[T any](value T) Option[T] {
	return Option[T]{true, value}
}

func None[T any]() Option[T] {
	return Option[T]{}
}
```

こちらにもモナド演算子を定義します。

```go:モナド演算子
func Unit[T any](value T) Option[T] {
	return Some(T)
}

func Bind[T, U any](src Option[T], f func(T) Option[U]) Option[U] {
	if src.hasValue {
		return f(src.value)
	} else {
		return None[U]()
	}
}
```

使用するコードのイメージ。型推論も効いていい感じです。

```go:使用
package main

import (
	"fmt"
	"option"
)

func main() {
	opt := option.Some(12)
	fmt.Println(opt)
	fmt.Println(option.Map(opt, func(v int) int64 {
		return int64(v)
	}))
	fmt.Println(option.Bind(opt, func(v int) option.Option[int64] {
		return option.Some(int64(v))
	}))
}
```

## モナドとして共通化する

この記事の本題。素直にモナドをインタフェースとして定義するなら次のようになります……が、Go のインタフェースはメソッド限定だし、Go のジェネリクスは高カインド型もメソッドに対する型パラメータも使えないのでこのコードはコンパイルできません。

```go:素直なモナドの定義（コンパイルできない）
package monad

// 仮に高カインド型を指定するような構文があったとして
type Monad[M type[any]] interface {
	Unit[T any](value T) M[T]
	Bind[T, U any](m M[T], f func(T) M[U]) M[U]
}
```

そこで高カインドにしたかった `M` は全て型引数を適用済みにし、各メソッドに定義したかった型パラメータもインターフェスの型パラメータにしてしまいます[^1]。こうすることで(一応)コンパイルは通ります[^2]。

[^1]: しれっと Unit の型引数がTからUに変わっていますが、こちらのほうがこの後のコードで便利だからです。
[^2]: コンパイルが通るかわりに、TとMT、UとMUが正しく紐づけられるかは実装側依存になります。どうにかしたかったのですがこれ以外の方法を思いつきませんでした…

```go:コンパイルが通るモナドの定義
package monad

type Monad[T, U, MT, MU any] interface {
	Unit(value U) MU
	Bind(m MT, f func(T) MU) MU
}
```

**モナド本体の型とは別に**、このインタフェースを満たすような型を用意します。 slice なら次の通り。
`Unit` 、 `Bind` メソッドの中身は先ほど定義した `Unit` 、 `Bind` 関数と同じです。

```go:sliceのモナド実装
package slice

type MonadImpl[T, U any] struct{}

func (MonadImpl[T, U]) Unit(value U) []U {
	return []U{value}
}

func (MonadImpl[T, U]) Bind(src []T, f func(T) []U) []U {
	var result []U
	for _, v := range src {
		result = append(result, f(v)...)
	}
	return result
}
```

インタフェースの満たし方がトリッキーなのですが、 `MonadImpl` の型引数に含まれていない `[]T` と `[]U` は、高カインド型引数*’だったこと’*になって、 `Monad` の第3・第4の型引数となります。

```go
var _ monad.Monad[int, bool, []int, []bool] = MonadImpl[int, bool]{}
```


Option も同様に実装できます。

```go:optionのモナド実装
package option

type MonadImpl[T, U any] struct{}

func (MonadImpl[T, U]) Unit(value U) Option[U] {
	return Some(T)
}

func (MonadImpl[T, U]) Bind(src Option[T], f func(T) Option[U]) Option[U] {
	if src.hasValue {
		return f(src.value)
	} else {
		return None[U]()
	}
}
```

これらの実装を使って、あらゆるモナドで使える `Map` 関数を定義してみます。
ポイントは、関数本体の引数に加えて `impl` というモナド演算子の実装を含む値を受け取るところです。

```go:Map関数
package main

import "monad"

func Map[T, U, MT, MU any, Impl monad.Monad[T, U, MT, MU]](impl Impl, src MT, f func(T) U) MU {
	return impl.Bind(src, func(value T) MU {
		return impl.Unit(f(value))
	})
}
```

さっそく使ってみようとすると…

```go:使ってみる
package main

import (
	"monad"
	"slice"
)

func Map[T, U, MT, MU any, Impl monad.Monad[T, U, MT, MU]](impl Impl, src MT, f func(T) U) MU {
	return impl.Bind(src, func(value T) MU {
		return impl.Unit(f(value))
	})
}

func main() {
	s1 := []int{1, 4, 7, 10}
	s2 := Map(slice.MonadImpl[int, bool]{}, s1, func(v int) bool {
		return v % 2 != 0
	})
	fmt.Println(s2)
}
```

> cannot infer MU

コンパイルエラーになりました。型が推論できないらしい。
Go の型引数は途中まで指定することができるので、推論できなかった `MU` を先頭に持って来て明示的に指定すればコンパイルが通ります。ちょっと不格好だけど仕方ないですね…

```go:MUを先頭に持って来る
package main

import (
	"monad"
	"slice"
	"option"
)

// MUを先頭に
func Map[MU, T, U, MT any, Impl monad.Monad[T, U, MT, MU]](impl Impl, src MT, f func(T) U) MU {
	return impl.Bind(src, func(value T) MU {
		return impl.Unit(f(value))
	})
}

func main() {
	s1 := []int{1, 4, 7, 10}
	// MU だけ明示的に指定
	s2 := Map[[]bool](slice.MonadImpl[int, bool]{}, s1, func(v int) bool {
		return v % 2 != 0
	})
	fmt.Println(s2)

	// もちろん Option でも同じコードが動く
	o1 := option.Some(12)
	o2 := Map[option.Option[bool]](option.MonadImpl[int, bool]{}, o1, func(v int) bool {
		return v % 2 != 0
	})
	fmt.Println(o2)
}
```

# まとめと感想

残念ながらダックタイピング性を大いに活用することはできませんでしたが、 Go のジェネリクスの表現力はだいたい分かった気になれました。ダックタイピングインタフェースとジェネリクスを組み合わせて活用するのはなかなか難しそうなので、何か思いつく方がいましたら教えてください。
最後に補足ですが、本記事でやっていることは**根本的にGoに向いていないこと**であり、実務を想定したコードではないことにご注意ください。