Goに高階カインドはない —— Goで書く実践圏論（3）

第1回で圏の公理を確かめ、第2回で標準ライブラリに潜む構造を取り出しました。今回は積み上げます。そして、積み上げた先で Go の型システムの天井に頭をぶつけます。

天井にぶつかる話を最後に置いたのは、それが今回いちばん実用的だからです。「Go には高階カインドがない」という話は、たいてい嘆きとして語られます。でもこれ、嘆く材料じゃなくて判断の材料です。回避策は3つあって、そのうち2つは実測で差が出ず、残り1つが1.8倍遅い。どれを選ぶかは、測ってから決めればいいです。

今回わかることを先に並べておきます。

この回は扱う話題が多いので、目的別の案内を置いておきます。検索から来た方はここを見て、必要な節まで飛ばしてください。

コードは前回までと同じリポジトリの part3/ にあります。

• https://github.com/makoto-developer/category-theory-go
• ブラウザですぐ試す: GitHub Codespaces で開く（Go を入れずに go test ./... が走ります）

インストールもログインも無しで、いますぐ手を動かしたいという方へ。下のサンドボックスは、この記事の山場を1ファイルに縮めたものです。同じ入力で Applicative は3件、Monad は1件しかエラーを返さないこと、同じ式木に代数を差し替えるだけで評価も整形も変数収集もできること、そして継続に恒等射を渡すと値が出てくることが、そのまま流れます。

このサンドボックスが動かしている main.go の正本は、リポジトリの examples/applicative-fold/main.go です。起動時に GitHub から取ってくる作りにしてあるので、リポジトリを直せばサンドボックスの中身も最新になります。

1. Functor → Applicative → Monad —— 何が増えるのか

1.1 3段の階層

第2回で Functor を見ました。「中身に射を適用し、外側の構造を保つ」ものでした。ここに2段積みます。

肝は Applicative と Monad の差です。

• Applicative: 3つの検証をやる。3つは互いに独立しているので、全部実行してから結果を合わせられる
• Monad: 3つの処理をやる。2番目は1番目の結果を使うので、1番目が失敗したら2番目は実行できない

「依存があるかないか」の差でしかありません。だが、この差がユーザーの見る画面を変えます。

1.2 蓄積できる結果型

(T, error) はエラーを1つしか持てません。複数持てる型を作ります。

// Validated は「値、または失敗の集まり」。失敗を蓄積できるのが (T, error) との違い。
type Validated[T any] struct {
	Value  T
	Errors []error
}

// Valid は成功した検証結果。
func Valid[T any](v T) Validated[T] { return Validated[T]{Value: v} }

// Invalid は失敗した検証結果。
func Invalid[T any](errs ...error) Validated[T] { return Validated[T]{Errors: errs} }

// OK は失敗が無いかを返す。
func (v Validated[T]) OK() bool { return len(v.Errors) == 0 }

// Err は蓄積した失敗を1つの error にまとめる。errors.Join がモノイドなのでこう書ける。
func (v Validated[T]) Err() error { return errors.Join(v.Errors...) }

Err() が errors.Join 一発で書けるのは、第2回 2.2 で見たとおり errors.Join がモノイドだからです（分岐に使うセンチネルの集合を固定した観測的等価性のもとで、という限定つきでした）。nil が単位元なので、失敗ゼロ件のときに nil が返ります。特別扱いが要りません。

Applicative の要になるのが、これです。

// Combine2 は2つの検証結果を合わせる。Applicative の要。
// 片方が失敗していても、もう片方の検証は済んでいるので、両方の失敗を集められる。
func Combine2[A, B, C any](a Validated[A], b Validated[B], f func(A, B) C) Validated[C] {
	if !a.OK() || !b.OK() {
		return Validated[C]{Errors: append(append([]error{}, a.Errors...), b.Errors...)}
	}
	return Valid(f(a.Value, b.Value))
}

対する Monad の bind。

// AndThen は Monad の bind。後段が前段の値に依存できる代わりに、
// 前段が失敗した時点で後段は走らないため、失敗はひとつしか集まらない。
func AndThen[A, B any](v Validated[A], f func(A) Validated[B]) Validated[B] {
	if !v.OK() {
		return Validated[B]{Errors: v.Errors}
	}
	return f(v.Value)
}

違いは引数の型に出ています。

• Combine2 は Validated[A] と Validated[B] を両方すでに持っている。だから両方の失敗を見られる
• AndThen は A を受け取って Validated[B] をこれから作る関数を取ります。A が無ければ関数を呼べないので、前段が失敗したら後段は存在すらしない

Monad が強いのは、後段が前段の値を使えるからです。そして失敗を1つしか集められないのも、まったく同じ理由によります。 表裏一体で、どちらかを選ぶしかありません。

1.3 実演 —— エラー3件 と エラー1件

登録フォームを両方で書きます。

// ValidateApplicative は3項目を独立に検証してから合わせる。
// 各検証が互いに依存しないので、失敗をすべて集められる。
func ValidateApplicative(name, email string, age int) Validated[Registration] {
	return Combine3(
		ValidateName(name),
		ValidateEmail(email),
		ValidateAge(age),
		func(n, e string, a int) Registration {
			return Registration{Name: n, Email: e, Age: a}
		},
	)
}

// ValidateMonadic は前段が成功したときだけ次に進む。
// 後段が前段の値を使えるかわりに、最初の失敗で打ち切られる。
func ValidateMonadic(name, email string, age int) Validated[Registration] {
	return AndThen(ValidateName(name), func(n string) Validated[Registration] {
		return AndThen(ValidateEmail(email), func(e string) Validated[Registration] {
			return MapV(ValidateAge(age), func(a int) Registration {
				return Registration{Name: n, Email: e, Age: a}
			})
		})
	})
}

3項目すべてが不正な入力を与えます。

// 3項目すべてが不正な入力。Applicative なら3件、Monad なら1件しか集まらない。
func TestApplicativeCollectsAllErrors(t *testing.T) {
	app := ValidateApplicative("", "no-at-mark", -1)
	mon := ValidateMonadic("", "no-at-mark", -1)

	if len(app.Errors) != 3 {
		t.Fatalf("Applicative が全部の失敗を集めていない: %d件 %v", len(app.Errors), app.Errors)
	}
	if len(mon.Errors) != 1 {
		t.Fatalf("Monad が途中で止まっていない: %d件 %v", len(mon.Errors), mon.Errors)
	}
	t.Logf("Applicative: %d件 -> %v", len(app.Errors), app.Err())
	t.Logf("Monad      : %d件 -> %v", len(mon.Errors), mon.Err())
}

Applicative: 3件 -> 名前が空です
    メールアドレスに @ が含まれていません
    年齢が負の数です
Monad      : 1件 -> 名前が空です

これがユーザーの見る画面です。

Monad 版では、ユーザーは名前を直して送信 → 「メールアドレスに @ がありません」→ 直して送信 → 「年齢が負の数です」。3往復します。Applicative 版なら1往復で済みます。

「フォームのバリデーションは全項目まとめて返せ」という UX の常識は、圏論の言葉にすると「その検証は Applicative 的に組め」ということになります。そして組めるかどうかの判定基準もはっきりしています。各項目の検証が互いに独立に走らせられるか。走らせられるなら Applicative 的に、前段の結果を見ないと後段が決まらないなら Monad 的に繋ぐしかありません。

一般論として読まないでください。 「Applicative はエラーを蓄積し、Monad は最初のエラーで止まる」は、Applicative と Monad の定義から出てくる性質ではありません。ここでそうなっているのは、今回の Validated を「Combine では両方の Errors を連結し、AndThen では失敗時に後段を呼ばない」という設計で実装したからです。Monad でも蓄積する作りにはできますし、Applicative でも最初の失敗で捨てる実装は書けます。

一般に言えるのはこちらです。独立して実行できる処理は Applicative 的に、前の結果を見ないと後段が決まらない処理は Monad 的に組む。 依存があると後段を先に走らせられないので、蓄積したくてもできる材料がない —— という構造の話であって、蓄積そのものは実装の選択です。

「依存」の意味も限定しておきます。Applicative でも、最終的な値が全部の入力に依存するのは当たり前にできます（Combine3 の合成関数が3つの値を全部使えます）。できないのは、前段の結果を見てから、後段にどの計算を置くかを選ぶことです。分かれ目はここだけです。

依存がある例も挙げておきます。

// 入力されたロールを確定させないと、次にどの権限検証を走らせるかが決まらない。
// 後段の「種類」が前段の結果で変わるので、Applicative では書けない。
AndThen(ValidateRole(raw), func(r Role) Validated[Permissions] {
    if r == RoleAdmin {
        return ValidateAdminScopes(raw)   // 管理者のときだけ走る
    }
    return ValidateUserScopes(raw)
})

「両方走らせて後から選べばいい」とはなりません。一般ユーザーの入力に管理者向けの検証をかければ、無関係な失敗が増えます。外部サービスを叩く検証なら、呼ぶ必要のない相手を呼ぶことにもなります。走らせるかどうかが前段の結果で決まる以上、先に走らせておくことができません。

肝は「両方の値が要る」ことではありません。前段の結果を見るまで、後段が何をするか決まらないことです。ここを取り違えると判定を誤ります。

訂正（2026-08-13）: 公開当初、ここに「パスワードとパスワード確認が一致するか」を依存の例として挙げ、「これは Applicative では書けない」と書いていました。書けるので、例として誤りでした。 一致判定が見るのは前段の結果ではなく生の入力なので、ValidateMatch(pw, confirm) という独立した検証を他の項目と並べて Combine すれば済みます。実際、フォームのバリデーションで「項目をまたぐルール」を独立した検証として並べるのは定石です。すぐ上の但し書きで「独立して実行できるかどうかが基準だ」と書いておきながら、その基準を満たさない例を出していました。

実務では両方混ざります。独立した項目は Applicative で束ね、前段の結果で後段の構造が決まる部分だけ Monad で繋ぐのが正解になります。

1.4 失敗件数の性質をテストする

Applicative が Monad より失敗を取りこぼさないことは、性質として書けます。

// 失敗の件数は、Applicative が常に Monad 以上になる。
func TestApplicativeNeverCollectsFewerErrors(t *testing.T) {
	rapid.Check(t, func(t *rapid.T) {
		name := rapid.SampledFrom([]string{"", "ok"}).Draw(t, "name")
		email := rapid.SampledFrom([]string{"", "bad", "a@b.com"}).Draw(t, "email")
		age := rapid.SampledFrom([]int{-1, 200, 30}).Draw(t, "age")

		app := ValidateApplicative(name, email, age)
		mon := ValidateMonadic(name, email, age)

		if len(app.Errors) < len(mon.Errors) {
			t.Fatalf("Applicative のほうが失敗を取りこぼした: app=%d, mon=%d", len(app.Errors), len(mon.Errors))
		}
		if app.OK() != mon.OK() {
			t.Fatalf("成否の判定が食い違った: app=%v, mon=%v", app.OK(), mon.OK())
		}
	})
}

成否の判定は一致し、失敗の件数だけが違う。これが Applicative と Monad の関係を最も正確に表しています。

1.5 ここで Go の制約が1つ目

Combine2 があるなら Combine3、Combine4 も要ります。

// Combine3 は3つ版。Go には可変長の型パラメータが無いので、数だけ書くことになる。
func Combine3[A, B, C, D any](a Validated[A], b Validated[B], c Validated[C], f func(A, B, C) D) Validated[D] {
	// ...
}

Go には可変長の型パラメータ（variadic type parameters）がありません。項目が5個なら Combine5 を書きます。TypeScript のタプル型や C++ のパラメータパックのような逃げ道はありません。

現実的な回避策は「フィールドごとに検証してエラーを []error に集め、最後に構造体を組む」という、型パラメータを使わない素朴な書き方です。

var errs []error
if name == "" {
    errs = append(errs, ErrNameEmpty)
}
// ...
if len(errs) > 0 {
    return errors.Join(errs...)
}

Applicative の構造としては同じことをしています。構造を理解していれば、素朴な書き方でも「独立な検証を全部走らせてから集める」形を意識的に守れる。ライブラリを持ち込む必要はありません。

2. F代数と fold —— 再帰を1か所に閉じ込める

2.1 木を扱うコードは、なぜ増殖するのか

式木、JSON、設定ファイルのツリー、AST。この手の構造を扱うと、似た再帰関数が並びます。

func Eval(e Expr) float64   { /* switch して再帰 */ }
func Print(e Expr) string   { /* switch して再帰 */ }
func Vars(e Expr) []string  { /* switch して再帰 */ }
func Depth(e Expr) int      { /* switch して再帰 */ }

4つの関数に、同じ形の switch と同じ形の再帰が4回書かれます。構成子を1つ足すと4か所直します。忘れると default に落ちて静かに壊れます。

2.2 再帰と解釈を分ける

分ければいいです。再帰の仕方と、各節点で何をするかを。

// Algebra は「各構成子をどう畳むか」の指定。圏論でいう F代数にあたる。
// 木の形（再帰の仕方）はここに現れず、Fold の側だけが知っている。
type Algebra[T any] struct {
	Num func(float64) T
	Var func(string) T
	Add func(T, T) T
	Mul func(T, T) T
}

// Fold は木を1回たどって T にする（catamorphism）。
// 再帰の書き方はここ1か所にしかないので、解釈を増やしても再帰は増えない。
func Fold[T any](e Expr, alg Algebra[T]) T {
	switch n := e.(type) {
	case Num:
		return alg.Num(n.V)
	case Var:
		return alg.Var(n.Name)
	case Add:
		return alg.Add(Fold(n.L, alg), Fold(n.R, alg))
	case Mul:
		return alg.Mul(Fold(n.L, alg), Fold(n.R, alg))
	}
	panic(fmt.Sprintf("未知の構成子: %T", e))
}

Algebra[T] の各フィールドの型に注目してほしいです。Add func(T, T) T であって、Add func(Expr, Expr) T ではありません。子はすでに畳まれて T になっている。だから代数の側に再帰は現れません。

この Algebra[T] がF代数、Fold がcatamorphismと呼ばれるものです。名前は厳めしいけれど、やっているのは「再帰を1か所に集めた」だけになります。

厳密に言うと、関手を $F(X)=\mathbb{R}+\mathrm{String}+X\times X+X\times X$（順に Num・Var・Add・Mul）と置いたとき、4つのフィールドをまとめた Algebra[T] は射 $F(T)\to T$ にあたります。直和からの射は、各成分からの射の組とちょうど同じものなので（第2回の Fanin がまさにこれでした）、1本の射を構造体の4フィールドにばらして持てるわけですね。

そして Fold が catamorphism になるのは、Expr がこの4つの構成子だけから作られた有限の木である範囲の話です。無限に伸びる木や、外から勝手に足された実装まで含めると、そうとは言えなくなります。

2.3 解釈を差し替える

// EvalAlgebra は式を評価する。
func EvalAlgebra(env map[string]float64) Algebra[float64] {
	return Algebra[float64]{
		Num: func(v float64) float64 { return v },
		Var: func(name string) float64 { return env[name] },
		Add: func(l, r float64) float64 { return l + r },
		Mul: func(l, r float64) float64 { return l * r },
	}
}

// PrintAlgebra は式を文字列にする。
var PrintAlgebra = Algebra[string]{
	Num: func(v float64) string { return fmt.Sprintf("%g", v) },
	Var: func(name string) string { return name },
	Add: func(l, r string) string { return "(" + l + " + " + r + ")" },
	Mul: func(l, r string) string { return "(" + l + " * " + r + ")" },
}

同じ木に、代数を差し替えて何度でも別の意味を与えられます。

// 同じ木を、代数を差し替えるだけで違うものに変換できる。再帰は Fold の中の1か所だけ。
func TestFoldInterpretsSameTreeDifferently(t *testing.T) {
	if got := Fold(sample, EvalAlgebra(env)); got != 15 {
		t.Fatalf("評価が違う: got=%v, want=15", got)
	}
	if got := Fold(sample, PrintAlgebra); got != "((x + 2) * (y + 3))" {
		t.Fatalf("整形が違う: got=%q", got)
	}
	if got := Fold(sample, VarsAlgebra); !slices.Equal(got, []string{"x", "y"}) {
		t.Fatalf("変数収集が違う: got=%v", got)
	}
	if got := Fold(sample, DepthAlgebra); got != 3 {
		t.Fatalf("深さが違う: got=%d, want=3", got)
	}
	if got := Fold(sample, CountAlgebra); got != 7 {
		t.Fatalf("節点数が違う: got=%d, want=7", got)
	}
}

5つの解釈があるが、再帰は Fold の中の1回しか書かれていない。構成子を足すときに直すのは Fold と Algebra の定義だけです。再帰と意味づけが分離できたことが、ここでの収穫です。

訂正（2026-08-08）: 公開当初、ここに「Algebra にフィールドが増えるので既存の代数がすべてコンパイルエラーになる」「書き漏らしがコンパイルエラーになる」と書いていました。これは誤りでした。

この記事の代数は Algebra[int]{Num: ..., Var: ..., Add: ..., Mul: ...} というキー付き struct literal で書いています。Go のキー付き literal はフィールドを省略できるので、Div を足しても既存のコードはそのままコンパイルが通ります。足りないフィールドは zero value、つまり nil のまま残り、alg.Div(...) を呼んだ瞬間に落ちます。コンパイル時ではなく実行時に発覚するわけです。

正しくはこうです。F代数は再帰と意味づけの分離には効きますが、構成子を足したときの網羅性検査までは Go の型システムから引き出せません。sealed ADT を持つ言語なら「構成子を足したら全部の分岐がコンパイルエラーになる」が成り立ちますが、Go で Algebra を構造体として表現しただけでは、そこには届きません。

第2回で嘆いた「switch の網羅性が検査されない」問題は、形を変えて残っています。switch の case 漏れが、構造体フィールドの nil に置き換わっただけです。どちらも実行時に落ちます。

これは第3回全体のテーマ —— Go の型システムには天井がある —— のもう一つの実例でもあります。網羅性が本当に欲しいなら、Algebra を構造体ではなくインターフェースにする（実装漏れがコンパイルエラーになる）か、Fold 側で nil を検査して早めに落とすことになります。

2.4 行き先は数値や文字列でなくてもよい

畳み込んだ結果が Expr でもかまいません。式の簡約がそのまま書けます。

// SimplifyAlgebra は畳み込みながら式を簡約する。
// 結果が Expr なので、fold の行き先は数値や文字列でなくてもよいと分かる。
var SimplifyAlgebra = Algebra[Expr]{
	Num: func(v float64) Expr { return Num{V: v} },
	Var: func(name string) Expr { return Var{Name: name} },
	Add: func(l, r Expr) Expr {
		ln, lok := l.(Num)
		rn, rok := r.(Num)
		switch {
		case lok && rok:
			return Num{V: ln.V + rn.V}
		case lok && ln.V == 0:
			return r
		case rok && rn.V == 0:
			return l
		}
		return Add{L: l, R: r}
	},
	// ... Mul も同様に、0倍と1倍を畳む
}

// 簡約の結果も Expr なので、そのまま次の fold に渡せる。
func TestSimplifyAlgebra(t *testing.T) {
	// (x * 1) + (0 * y) + 3 は x + 3 になる
	e := Add{
		L: Add{L: Mul{L: Var{Name: "x"}, R: Num{V: 1}}, R: Mul{L: Num{V: 0}, R: Var{Name: "y"}}},
		R: Num{V: 3},
	}

	simplified := Fold(e, SimplifyAlgebra)

	if got := Fold(simplified, PrintAlgebra); got != "(x + 3)" {
		t.Fatalf("簡約が効いていない: got=%q", got)
	}
	if got := Fold(simplified, CountAlgebra); got != 3 {
		t.Fatalf("節点数が減っていない: got=%d, want=3", got)
	}
}

7節点が3節点になりました。そして重要なのは、簡約しても評価結果が変わらないことを性質として書けることです。

// 簡約しても評価結果は変わらない（意味を保つ変換になっている）。
func TestSimplifyPreservesMeaning(t *testing.T) {
	rapid.Check(t, func(t *rapid.T) {
		e := genExpr(t, 4)

		before := Fold(e, EvalAlgebra(env))
		after := Fold(Fold(e, SimplifyAlgebra), EvalAlgebra(env))

		if before != after {
			t.Fatalf("簡約で意味が変わった: before=%v, after=%v", before, after)
		}
	})
}

ランダムな式木を作って、簡約前後で評価結果が一致することを確かめます。最適化パスの正しさを、こういう形で機械的に検証できる。コンパイラやクエリオプティマイザを書くなら、この形のテストが効きます。

2.5 代数そのものを合成する

F代数を使ういちばんの利点は、ここだと思います。代数どうしを合成できる。

// ProductAlgebra は2つの代数を1つにまとめる。木を1回たどるだけで両方の答えが出る。
// 代数そのものが合成できる、というのがF代数を使ういちばんの利点。
func ProductAlgebra[A, B any](a Algebra[A], b Algebra[B]) Algebra[Pair[A, B]] {
	return Algebra[Pair[A, B]]{
		Num: func(v float64) Pair[A, B] { return Pair[A, B]{a.Num(v), b.Num(v)} },
		Var: func(name string) Pair[A, B] { return Pair[A, B]{a.Var(name), b.Var(name)} },
		Add: func(l, r Pair[A, B]) Pair[A, B] {
			return Pair[A, B]{a.Add(l.First, r.First), b.Add(l.Second, r.Second)}
		},
		Mul: func(l, r Pair[A, B]) Pair[A, B] {
			return Pair[A, B]{a.Mul(l.First, r.First), b.Mul(l.Second, r.Second)}
		},
	}
}

「評価しながら節点数も数える」が、木を1回たどるだけでできます。しかも EvalAlgebra にも CountAlgebra にも手を入れていません。

// 代数の積: 木を1回たどるだけで2つの答えが同時に出る。
func TestProductAlgebraMatchesTwoFolds(t *testing.T) {
	rapid.Check(t, func(t *rapid.T) {
		e := genExpr(t, 4)

		both := Fold(e, ProductAlgebra(EvalAlgebra(env), CountAlgebra))
		wantEval := Fold(e, EvalAlgebra(env))
		wantCount := Fold(e, CountAlgebra)

		if both.First != wantEval || both.Second != wantCount {
			t.Fatalf("積代数の結果が食い違う: got=%+v, want=(%v,%d)", both, wantEval, wantCount)
		}
	})
}

第2回で見た「積の普遍性」がここで働いています。$T$ への代数と $U$ への代数があれば、$T\times U$ への代数が自動的に決まります。

2.6 値段を測る

// 代数を経由する fold と、手書きの再帰の差。抽象化の代金を測る。
func BenchmarkFoldVsDirect(b *testing.B) {
	e := deepExpr(12)
	alg := EvalAlgebra(env)

	b.Run("fold", func(b *testing.B) {
		for b.Loop() {
			sinkFloat = Fold(e, alg)
		}
	})
	b.Run("direct", func(b *testing.B) {
		for b.Loop() {
			sinkFloat = EvalDirect(e, env)
		}
	})
}

深さ12の完全二分木（4,095 節点）で測りました。

1.6倍遅い。代数のフィールドが関数値なので、節点ごとに間接呼び出しが入るためです。アロケーションはどちらもゼロ。

代数の積の効果も測ります。

1.26倍速い。2回が1回になったのに2倍にならないのは、Pair の組み立てと2つの代数の呼び出しが残るからです。

2.7 判断

• 解釈が2〜3個以下で、構成子がめったに増えないなら手書きでよい。1.6倍は無視できない
• 解釈が増え続けるなら F代数が勝つ。解釈を10個書いても再帰は1つのまま。ただし構成子を足したときの書き漏らしは、コンパイラでは止まらない（2.3 の訂正を参照）
• AST の最適化パスを書くなら、意味保存のテストが property-based で書けることが決定的

実務で当てはまるのは、SQL のクエリビルダ、テンプレートエンジン、設定 DSL、フィーチャーフラグの条件式あたりでしょう。「同じ木を、評価もするし、可視化もするし、静的検査もする」構造なら F代数が効きます。

3. iter.Seq は継続渡しに似ている

3.1 Go 1.23 が持ち込んだもの

Go 1.23 の range-over-func で、iter.Seq はこう定義されました。

type Seq[V any] func(yield func(V) bool)

「値の列」が、関数を受け取る関数として定義されています。奇妙に見えますが、これは継続渡し形式（CPS）によく似た形をした push 型イテレータです。

// Cont は継続渡し形式の値。「A を持っている」ことを「A を受け取る関数を受け取れる」で表す。
// iter.Seq[V] = func(yield func(V) bool) も、打ち切り可能な継続を取るこの形をしている。
type Cont[R, A any] func(func(A) R) R

// ToCont は値を継続渡しに変える。この向きの変換はいつでもできる。
func ToCont[R, A any](a A) Cont[R, A] {
	return func(k func(A) R) R { return k(a) }
}

// FromCont は継続に恒等射を渡して値を取り出す。R を A に固定できるときだけ書ける。
// なお ToCont・FromCont は片道で戻るだけで、Cont[A,A] 全体との同型ではない（3.2 を参照）。
func FromCont[A any](c Cont[A, A]) A {
	return c(func(a A) A { return a })
}

FromCont の実装が面白い。継続に恒等射を渡すと、値が出てくる。FromCont(ToCont[A](a)) == a は常に成り立ちます。

3.2 ただし、これは米田の補題そのものではない

訂正（2026-08-08）: 公開当初、ここに「これが米田の補題のいちばん噛み砕いた姿で、$A$ と Cont[A,A] は同じ情報量を持つ」と書いていました。同型ではありません。

反例がすぐ作れます。

// これも Cont[int, int] だが、継続を無視して定数を返す。
var ignore Cont[int, int] = func(k func(int) int) int { return 42 }

FromCont(ignore) は 42 を返します。しかし ToCont[int](42) は「継続を必ず 42 に適用する関数」であって、ignore（継続を捨てる関数）とは別物です。往復して戻ってきません。Cont[A,A] には、継続を無視するものや、継続を複数回呼ぶものが含まれています。$A$ より広いのです。

米田の補題が対応させているのは、$R$ を1つに固定したものではなく、

のように、任意の行き先 $R$ に対して自然に振る舞う多相的な継続です。「任意の $R$ で自然」という条件が、上のような「継続を無視する関数」を除外します。Go の型システムでは、この自然性を型で表現できません。Cont[A, A] と書いた時点で $R$ は固定されてしまい、条件が落ちています。

言えるのはここまでです。

• iter.Seq は CPS 的な形をした push 型イテレータとして理解できる
• 「値を持つこと」と「値に対して何ができるかを知っていること」の間に深い対応がある、というのが米田の補題の勘所
• ただし Go の Cont[A,A] 全体と A が同型になるわけではないし、iter.Seq を米田の補題と同一視してもいけない

3.3 Functor 則もそのまま成り立つ

// MapCont は継続渡しの上の Functor。継続の側を先に加工する。
func MapCont[R, A, B any](c Cont[R, A], f func(A) B) Cont[R, B] {
	return func(k func(B) R) R {
		return c(func(a A) R { return k(f(a)) })
	}
}

値を加工する代わりに、継続を加工している。向きが逆になっているのに、外から見ると同じ Functor に見えます。

// 継続渡しの上でも Functor 則が成り立つ。
func TestContFunctorLaws(t *testing.T) {
	rapid.Check(t, func(t *rapid.T) {
		n := rapid.Int().Draw(t, "n")
		c := ToCont[int](n)

		if got := FromCont(MapCont(c, func(x int) int { return x })); got != n {
			t.Fatalf("恒等の保存が破れた: got=%d", got)
		}

		f := func(x int) int { return x * 3 }
		g := func(x int) int { return x - 1 }

		twice := FromCont(MapCont(MapCont(c, f), g))
		fused := FromCont(MapCont(c, func(x int) int { return g(f(x)) }))

		if twice != fused {
			t.Fatalf("合成の保存が破れた: 2回=%d, 合成=%d", twice, fused)
		}
	})
}

だから iter.Seq に対する Map を何段重ねても、中間のスライスは生まれません。第2回で見た「iter.Seq では融合が自動で起きる」のは、この構造によるものです。CPS 的に書くと、加工が継続の側に積まれていき、最後に一度だけ流れる。

3.4 push と pull

iter.Seq は push 型です。列の側が「はい次、はい次」と値を押し込んできます。呼び出し側は yield の中でしか値を受け取れません。

// push 型は「呼ばれる側が制御を持つ」ので、途中で止めるには打ち切りの合図が要る。
func TestSeqStopsOnBreak(t *testing.T) {
	produced := 0
	seq := func(yield func(int) bool) {
		for i := range 100 {
			produced++
			if !yield(i) {
				return
			}
		}
	}

	var got []int
	for v := range seq {
		got = append(got, v)
		if len(got) == 3 {
			break
		}
	}

	if produced != 3 {
		t.Fatalf("打ち切りが効いていない: 生成数=%d, want=3", produced)
	}
}

yield の戻り値 bool が打ち切りの合図になっています。break すると yield が false を返し、生成側が止まります。100要素あるのに3つしか作られません。

対して pull 型は、こちらから「次をくれ」と要求する形です。標準ライブラリの iter.Pull が変換してくれます。

// SumPull は iter.Pull で pull 型に変換してから畳み込む。
// push と pull は相互に変換できるが、変換にはコルーチンの切り替えが要る。
func SumPull(seq iter.Seq[int]) int {
	next, stop := iter.Pull(seq)
	defer stop()

	total := 0
	for {
		v, ok := next()
		if !ok {
			return total
		}
		total += v
	}
}

理論上、push と pull は相互に変換できます。同じ列を表しています。だが実行コストはまったく違う。

3.5 測ったら120倍だった

要素あたりに直すと、スライス 0.27 ns、push 1.28 ns、pull 33 ns。

push 型のオーバーヘッドは要素あたり 1 ns。iter.Seq を返す API を書くことに、性能上の反対理由はほぼありません。

pull 型は2桁遅い。100,000要素で 3.3 ミリ秒。同じ処理がスライスなら 27 マイクロ秒です。

差の出どころは制御の往復です。push 型は「列の側が主導権を持ち、要素ごとに yield を呼ぶ」だけなので、実体はただの関数呼び出しです。ところが pull 型では、呼ぶ側が next() で要求する形に主従が逆転します。iter.Pull はこの反転を、内部にコルーチン（runtime のゴルーチン切り替え機構）を1つ立てて実現しています。

つまり next() を1回呼ぶたびに、呼び出し側と、列を走らせる側との間で制御が往復します。行きと帰りで2回、実行中のスタックそのものを差し替えることになります。この往復が、要素あたり 1 ns の関数呼び出しに対して 33 ns という差になっています。

なお、この切り替えは runtime.coroswitch によるもので、スケジューラを介さない直接の受け渡しです（runtime/coro.go）。チャネルで待ち合わせるときのような park は起きず、goroutine が積まれて順番待ちすることもありません。それでもなお、ただの関数呼び出しの30倍かかります。「スタックを切り替える」こと自体が、関数を1回呼ぶのとは桁の違う仕事だということですね。

これは実務でそのまま効く指針になります。

iter.Pull は、pull でなければ書けない処理にだけ使う。

pull が必要なのは、2本の列をマージする（両方を同時に進める）、先読みして判断する、といった「複数の列の進行を自分で制御したい」場面です。単に「イテレータが欲しい」だけなら push 型のまま使います。

そして、ここでも第2回と同じ教訓が出てきます。

同型であることと、同じコストであることは別です。

push と pull は情報として等価ですが、実行コストは要素あたり 1.28 ns 対 33 ns、26倍違います（スライスを直に走査するのと比べれば 120倍です）。圏論は「変換できる」ことを教えてくれますが、「変換すべきか」は教えてくれません。そこは測るしかありません。

4. 天井 —— Go に高階カインドはない

4.1 書けない宣言

ここまで、[]T、*T、iter.Seq[T]、(T, error)、Validated[T]、Cont[R,T] と、いくつもの Functor を見てきました。全部「map できる」という同じ性質を持っています。

だから、こう書きたくなります。

// 書けない
type Functor[F[_] any] interface {
	Map[A, B any](fa F[A], f func(A) B) F[B]
}

書けません。Go の型パラメータは型しか受け取れず、「型を取って型を返すもの」（[]、*、Option のような型構築子）を受け取れません。これが高階カインド多相（higher-kinded polymorphism）が無いということです。

Haskell では Functor f と書けます。Scala には F[_] があります。Rust にも無い（GAT で部分的に代替される）。Go にはありません。

結果として何が起きるか。「すべての Functor に対して一度だけ書く」ができない。第2回で MapSlice、MapPtr、MapSeq、MapErr を別々に書いたのは、まとめられなかったからです。

4.2 3つの凌ぎ方

回避策1: 型を消す

// AnyFunctor は要素の型を any に潰して「map できるもの」を表す。
// F を抽象化できない代わりに、A と B を抽象化しないことで辻褄を合わせる。
type AnyFunctor interface {
	MapAny(f func(any) any) AnyFunctor
}

// AnySlice は AnyFunctor を満たすスライス。
type AnySlice []any

func (s AnySlice) MapAny(f func(any) any) AnyFunctor {
	out := make(AnySlice, len(s))
	for i, v := range s {
		out[i] = f(v)
	}
	return out
}

F を抽象化する代わりに、A と B を any に潰します。インターフェースで統一できるが、型安全性が消え、any への箱詰めが起きる。

回避策2: 具体型ごとに書く

// MapSliceGeneric は要素型だけをジェネリックにする。実用上いちばん素直な方法で、
// 型安全もアロケーションも問題ない。ただし F の種類だけ関数が増える。
func MapSliceGeneric[A, B any](xs []A, f func(A) B) []B {
	out := make([]B, len(xs))
	for i, x := range xs {
		out[i] = f(x)
	}
	return out
}

要素型だけをジェネリックにします。型安全で速い。ただし F の種類だけ関数が増えます。

回避策3: 辞書を渡す

// FunctorDict は F[A] と F[B] を別々の型パラメータに分けることで、
// 高階カインドなしに「どの Functor で写すか」を引数にする。
type FunctorDict[FA, FB, A, B any] struct {
	Map func(FA, func(A) B) FB
}

// SliceFunctor はスライス用の辞書。
func SliceFunctor[A, B any]() FunctorDict[[]A, []B, A, B] {
	return FunctorDict[[]A, []B, A, B]{Map: MapSliceGeneric[A, B]}
}

// MapTwiceWith は辞書を受け取って「2回写す」処理を Functor によらず書く。
// これが高階カインドの代わりにできる範囲の上限である。
func MapTwiceWith[FA, FB, FC, A, B, C any](
	d1 FunctorDict[FA, FB, A, B],
	d2 FunctorDict[FB, FC, B, C],
	fa FA, f func(A) B, g func(B) C,
) FC {
	return d2.Map(d1.Map(fa, f), g)
}

F[A] と F[B] を別々の型パラメータにして、両者を繋ぐ Map の実装を値として渡します。これで「Functor によらない処理」が書けます。

// 辞書渡しなら、Functor の種類を引数で差し替えられる。
// 高階カインドがあれば1本で書けるところを、辞書を渡すことで近いことをしている。
func TestDictionaryAbstractsOverFunctor(t *testing.T) {
	double := func(n int) int { return n * 2 }

	fromSlice := MapTwiceWith(
		SliceFunctor[int, int](), SliceFunctor[int, string](),
		[]int{1, 2}, double, strconv.Itoa,
	)
	if !slices.Equal(fromSlice, []string{"2", "4"}) {
		t.Fatalf("スライスの結果が違う: %v", fromSlice)
	}

	fromOption := MapTwiceWith(
		OptionFunctor[int, int](), OptionFunctor[int, string](),
		Option[int]{Value: 3, Some: true}, double, strconv.Itoa,
	)
	if !fromOption.Some || fromOption.Value != "6" {
		t.Fatalf("Option の結果が違う: %+v", fromOption)
	}
}

MapTwiceWith の本体は Functor の種類を知りません。スライスにも Option にも同じコードが使えます。Haskell なら fmap g . fmap f で済むところを、辞書を2つ引数で渡すことで実現している。

実は、これは Haskell のコンパイラが型クラスに対して内部でやっていること（辞書渡し変換）と同じです。Haskell では暗黙に渡される辞書を、Go では手で渡します。それだけの差だとも言えます。

4.3 コストを測る

1,000要素の []int を []string に写します。

ジェネリクスと辞書渡しは、手書きループと同じコストです。 抽象化のペナルティがゼロ。

型消去だけが 1.8倍遅く、アロケーションが2倍になります。any への箱詰めが要素ごとに発生するためだ（901 → 1,902 の増分がちょうど1,000個の boxing にあたる）。

結論は明快です。

高階カインドの代わりに any を選ぶ理由は、性能の面ではありません。

any を使うのは、辞書渡しの型パラメータが多すぎて読めない、という可読性の理由に限られます。そしてその可読性も、1.8倍の速度と2倍のアロケーションに見合うかを考えるべきです。

4.4 もう一つの天井 —— メソッドに型パラメータが付けられない

第2回でも触れた制約を、もう一度正面から見ます。

// 書けない
func (o Option[A]) Map[B any](f func(A) B) Option[B]

メソッドに新しい型パラメータ B を導入できません。これは golang/go#49085 で議論されている既知の制約です。

理由は「型理論として不可能だから」ではありません。Go の暗黙的なインターフェース充足と組み合わせたとき、必要なジェネリックメソッドの実体化をいつ・どこで生成すべきかが決まらなくなる、というコンパイルモデル側の制約です。ある型がインターフェースを満たすかどうかを宣言なしに判定する以上、どの型引数の組み合わせでコードを生成しておけばよいかが、事前コンパイルでは分からなくなります。

実用上の影響は、メソッドチェーンが書けないこと。

// 書きたい
result := opt.Map(parse).Map(validate).Map(format)

// 書けるのはこれ
result := MapOption(MapOption(MapOption(opt, parse), validate), format)

読み順が内側から外側になります。3段でもう厳しく、5段書くと誰も読めません。

これが Go で「関数型スタイル」が流行らない最大の理由だと思います。合成そのものは書けるのに、書いたものが読めないんです。第4回 3.1 では、この読みにくさを避けるためにステップの型を State → State にそろえて、スライスに並べるという折り合いをつけます。型を変えないと決めれば、ネストではなくリストで書けるからです。ただしその代償も同じ回で測ります。

4.5 で、Go でどこまでやるべきか

正直な線引きを書いておきます。

やる価値があること

• 具体的な型ごとに Map、Filter、Reduce を書くこと（回避策2）。型安全で、実測では素の実装と差が出ない
• 法則をテストで確認すること。property-based test は安い投資で効果が大きい
• 「これは Functor か」「これはモノイドか」と問うこと。構造の名前を知っていること自体に価値がある

やらないほうがいいこと

• any で Functor を統一すること。1.8倍のコストに見合わない
• 辞書渡しをアプリケーションコードに持ち込むこと。型パラメータが6個並ぶ関数はレビューを通らない
• Haskell の do 記法に相当するものを Go で再現しようとすること。ネストが深くなるだけ

Go における圏論の使い方は、抽象化のためではなく、判断のためです。 「この処理は独立か（Applicative か）」「この集計は分割できるか（モノイドか）」「この middleware は包む相手の中身に依存していないか（一様で再利用できるか）」。問いを立てる道具として使うのがいちばん実入りがいい。

5. 随伴 —— Functional Option パターンを支える同型

5.1 カリー化の同型

第2回の最後に置いた伏線を回収します。

「2引数関数」と「1引数関数を返す1引数関数」が同じものだという同型。この形の対応を随伴（adjunction）と呼びます。「積を取る」操作と「関数型を作る」操作が、互いに随伴の関係にあります。

抽象的に見えるが、Go のコードで毎日見ています。

5.2 Functional Option パターン

// ServerOption は設定を書き換える射。Config → Config の自己射になっている。
type ServerOption func(ServerConfig) ServerConfig

func WithHost(h string) ServerOption {
	return func(c ServerConfig) ServerConfig { c.Host = h; return c }
}

// NewServer は既定値に ServerOption を順に適用する。
// ServerOption は Config → Config の自己射なので、その全体は合成に関してモノイドをなす。
// 引数ゼロなら既定値がそのまま出るのは、恒等射が単位元として働くから。
func NewServer(opts ...ServerOption) ServerConfig {
	c := ServerConfig{Host: "localhost", Port: 8080, Timeout: 30 * time.Second}
	for _, opt := range opts {
		c = opt(c)
	}
	return c
}

WithHost の型を見てほしいです。func(string) ServerOption、つまり func(string) func(ServerConfig) ServerConfig です。

これは func(ServerConfig, string) ServerConfig をカリー化したものです。

// SetHost は「設定と値の組」を受け取る形。ServerOption とはカリー化で行き来できる。
func SetHost(c ServerConfig, h string) ServerConfig { c.Host = h; return c }

// CurryOption は SetHost のような2引数の設定関数を ServerOption に変える。
// func(Config, A) Config ≅ func(A) func(Config) Config という同型が
// Functional Option パターンを支えている同型である（積と冪の随伴）。
func CurryOption[A any](f func(ServerConfig, A) ServerConfig) func(A) ServerOption {
	return func(a A) ServerOption {
		return func(c ServerConfig) ServerConfig { return f(c, a) }
	}
}

// カリー化すると、2引数の設定関数がそのまま ServerOption になる。
func TestCurryOptionMatchesDirectSetter(t *testing.T) {
	withHost := CurryOption(SetHost)

	rapid.Check(t, func(t *rapid.T) {
		host := rapid.StringMatching(`[a-z]{1,8}`).Draw(t, "host")

		curried := NewServer(withHost(host))
		direct := SetHost(NewServer(), host)

		if curried != direct {
			t.Fatalf("カリー化した設定と直接の設定が食い違う: %+v vs %+v", curried, direct)
		}
	})
}

引数を取る Functional Option の典型は、2引数の設定関数をカリー化したものです。 そしてカリー化できるのは、積と冪の間に随伴があるからです。

「Functional Option とはカリー化のことだ」とまでは言えません。WithDebug() のように引数を取らない Option もありますし、渡された値をそのまま入れるとは限らない Option も書けます。パターンの本体は「設定変更を Config → Config という自己射の値にして、合成できるようにした」ことのほうです。カリー化が説明してくれるのは、なぜ WithHost(h) があの二段の形をしているのかという部分になります。

5.3 だから Option はモノイドになる

カリー化した結果、ServerOption は ServerConfig → ServerConfig という自己射になりました。自己射の集まりは、合成に関してモノイドをなす（第2回 4.1 で middleware について見たとおり）。

だから、こうできます。

// ApplyOptions は ServerOption を1本にまとめる。Chain（middleware）と同じ構造。
func ApplyOptions(opts ...ServerOption) ServerOption {
	return func(c ServerConfig) ServerConfig {
		for _, opt := range opts {
			c = opt(c)
		}
		return c
	}
}

// ServerOption の全体はモノイド。まとめ方を変えても結果は同じ（結合律）。
func TestOptionsAreMonoid(t *testing.T) {
	rapid.Check(t, func(t *rapid.T) {
		// ...
		flat := NewServer(WithHost(host), WithPort(port), WithTimeout(time.Second))
		grouped := NewServer(ApplyOptions(WithHost(host), WithPort(port)), WithTimeout(time.Second))
		nested := NewServer(WithHost(host), ApplyOptions(WithPort(port), WithTimeout(time.Second)))

		if flat != grouped || flat != nested {
			t.Fatalf("結合律が破れた: 平坦=%+v, 前2つ=%+v, 後2つ=%+v", flat, grouped, nested)
		}
	})
}

「本番用の設定セット」を ApplyOptions で1つにまとめ、呼び出し側でさらにオプションを足せます。middleware の Chain とまったく同じ構造です。

var productionDefaults = ApplyOptions(WithTimeout(5*time.Second), WithPort(443))

srv := NewServer(productionDefaults, WithHost("api.example.com"))

そして順序には意味がある（非可換）。

// 同じ項目を2回設定すると後勝ち。可換ではないので順序には意味がある。
func TestOptionsAreNotCommutative(t *testing.T) {
	forward := NewServer(WithPort(1), WithPort(2))
	reversed := NewServer(WithPort(2), WithPort(1))

	if forward == reversed {
		t.Fatal("順序を入れ替えても同じになった（可換になっている）")
	}
}

後勝ちになるのは、ServerOption が「上書きする射」だからです。もし「まだ設定されていなければ設定する」実装にすれば先勝ちになります。どちらが正しいかはドメインが決めることだが、どちらであるかを意識せずに書かれた Option は事故の元になる。

5.4 同じ構造が3回出てきた

ここまでで、まったく同じ構造が3つ出てきました。

3つとも「対象への自己射のモノイド」です。だから3つとも、括り方は自由で、順序は自由でなく、空なら素通しになります。

別々に覚えていた3つのパターンが、1つの構造だと分かる。これが圏論を学ぶことの、いちばん現実的な効き目だと思います。新しい道具は増えない。だが、すでに持っている道具が整理されます。

6. まとめ

Applicative と Monad

• Applicative は独立した値を合わせる、Monad は前の結果に依存して次を決めます。この差だけ
• 同じ入力でエラーが 3件 と 1件。フォームのバリデーションで往復回数が変わる
• 成否の判定は一致し、失敗の件数だけが違う
• 「独立した項目は Applicative で束ね、前段の結果で後段の構造が決まる部分だけ Monad で繋ぐ」が実務の正解。分かれ目は「両方の値が要るか」ではなく「前段を見ないと後段が決まらないか」
• Go には可変長の型パラメータが無いので Combine2/3/4 を書き並べることになります。素朴に []error を集める書き方でも構造は同じ

F代数と fold

• 再帰の仕方と各節点の解釈を分けます。再帰は Fold の中の1か所だけになる
• 解釈を差し替えれば、評価・整形・変数収集・深さ・節点数・簡約が全部書ける
• ただし網羅性は Go の型システムから引き出せない。キー付き struct literal はフィールドを省略できるので、構成子を足しても既存の代数はコンパイルが通り、nil のまま実行時に落ちる。switch の網羅性問題は解決ではなく、形を変えて残っている
• 代数の積で、木を1回たどるだけで2つの答えが出る（1.26倍速）
• 代金は手書き再帰の 1.6倍。解釈が2〜3個なら手書き、増え続けるなら F代数
• 簡約の意味保存を property-based test で検証できます。最適化パスを書くなら決定的

iter.Seq と CPS

• iter.Seq[V] = func(yield func(V) bool) は継続渡し形式。「値を持っている」を「値を受け取る関数を受け取れる」で表す
• 継続に恒等射を渡すと値が出てくる。ただし逆向きは戻らないので、Cont[A,A] と A は同型ではない。米田の補題が要求する「任意の $R$ での自然性」を Go の型では書けないため（3.2 の訂正を参照）
• CPS では加工が継続の側に積まれるので、中間スライスが生まれない
• スライス直走査が要素あたり 0.27 ns、push が 1.28 ns、pull（iter.Pull）が 33 ns。pull はスライス比で 120倍以上、push 比でも 26倍遅い
• iter.Pull は、pull でなければ書けない処理（マージ、先読み）にだけ使う
• 同型であることと、同じコストであることは別だ

高階カインドの不在

• Functor[F[_]] は書けません。「すべての Functor に対して一度だけ書く」ができない
• 回避策は3つ。型消去（any）、具体型ごとに書く、辞書渡し
• ジェネリクスと辞書渡しは手書きループと同じコスト。型消去だけが 1.8倍遅く、アロケーション2倍
• メソッドに型パラメータを付けられないので、メソッドチェーンになりません。これが Go で関数型スタイルが流行らない最大の理由
• Go における圏論の使い方は、抽象化のためではなく判断のため

随伴

• カリー化は積と冪の随伴（固定した $B$ について $(-)\times B⊣(-{)}^B$）。引数付きの Functional Option があの二段の形をしている理由がこれ。ただしパターン全体がカリー化だというわけではない
• カリー化の結果、Option は自己射になり、その全体がモノイドになります。だから ApplyOptions でまとめられる
• middleware・Functional Option・比較関数は、すべて「自己射のモノイド」という同じ構造。括り方は自由、順序は自由でない、空なら素通し

次回は最終回。ここまでの道具を全部使って、実際に動くワークフローエンジンを組みます。素直な手続き型の実装と圏論的な実装を両方書いて、行数・アロケーション・レイテンシ・テストの手間を比較します。

そして正直に書きます。どこで得をして、どこで壊れたかを。型でステップの順序を守ることを諦めた場所、スタックトレースが深くなってステップ名が出なくなった場所、これはレビューを通らないと判断した場所。抽象化の代金は性能だけではありません。

（次回「圏論でワークフローエンジンを組み直したら1ステップ30ns —— Goで書く実践圏論（4）」に続く）

この記事のコード: part3/ — 何を実行して何を見ればいいかは、そのディレクトリの README にまとめてあります。Codespaces で開けばそのまま動きます。

連載一覧

1. Goの関数と型は圏をなす
2. errors.Join はモノイドである
3. Goに高階カインドはない（本記事）
4. 圏論でワークフローエンジンを組み直したら1ステップ30ns