# 圏論でのステートマシン
ステートマシンの構造
- 状態の集合 $S$
- 入力の集合（アルファベット） $\Sigma$
- 遷移関数 $\delta: S \times \Sigma \to S$
- 初期状態 $s_0 \in S$
- （必要に応じて）受理状態の集合 $F \subseteq S$
圏論でのステートマシンの捉え方
- (a) 状態遷移を射と見る
- 各状態を**対象（object）**として、
- 各入力に対応する遷移を**射（morphism）**とみなす。
- これにより、ステートマシンを**小さな圏（small category）**と見なせる。
- (b) オートマトンを圏の圏として考える
- 状態遷移システムを、**自由圏（free category）**として定式化できる。
- 例えば、アルファベット $\Sigma$ による遷移を生成元とする有向グラフから自由圏を作り、そこに関手を定義して実際の動作を表現する。
- (c) 状態遷移を関手として考える
- ステートマシンの振る舞いは、ある入力文字列の圏（たとえば自由モノイド $\Sigma^*$）から状態遷移の圏への関手とみなせる。
- これは「入力の列 → 状態の遷移の列」という構造保存的マッピングである。
まとめ
| **観点** | **圏論での対応** |
| -------------------- | ------------------------------------------------ |
| 状態 | 対象（Object） |
| 遷移 | 射（Morphism） |
| 入力系列 | モノイド（自由圏） |
| ステートマシン全体 | 関手（Functors）または圏 |
| 状態遷移の論理的挙動 | ナチュラルトランスフォーメーションやコアルゲブラ |
## システム開発への応用
| **圏論概念** | **システム開発での意味** |
| ------------------ | ---------------------------------------------- |
| **対象 (Object)** | 状態・データ型・画面など |
| **射 (Morphism)** | 処理・変換・イベント遷移など |
| **関手 (Functor)** | モデル間の写像、状態から画面への写像など |
| **自然変換** | モデルバージョン間の変換、差分の表現など |
| **圏の合成性** | 部分システムの結合やモジュール化の理論的裏付け |
## Haskellで圏論的ステートマシンを表現する
1. 型による状態の表現
```haskell
-- 状態（対象）
data State = Draft | Review | Published deriving (Show, Eq)
-- イベント（射）
data Event = Submit | Approve | Reject deriving (Show, Eq)
```
2. 遷移関数（射の合成）を定義
```haskell
-- 遷移関数：状態 × イベント → Maybe 状態（合成可能かどうか）
transition :: State -> Event -> Maybe State
transition Draft Submit = Just Review
transition Review Approve = Just Published
transition Review Reject = Just Draft
transition _ _ = Nothing -- 合成不可能な射（無効な遷移）
```
3. 遷移の合成を使ってトレース
```haskell
-- 入力イベント列に対する遷移をたどる
runTransitions :: State -> [Event] -> Maybe State
runTransitions = foldl (\acc e -> acc >>= (`transition` e)) . Just
```
```haskell
-- 実行例
main :: IO ()
main = do
let events = [Submit, Approve]
let result = runTransitions Draft events
print result -- Just Published
```
4. 圏論的な構造を抽象化（拡張）
さらに、状態遷移の構造を型クラスで一般化しておくと、再利用性が高まる。
```haskell
class CategoryLike s e where
transition' :: s -> e -> Maybe s
```
```haskell
instance CategoryLike State Event where
transition' = transition
```
5. モナドとの相性：履歴付きのトレース
```haskell
type Trace = [(State, Event)]
runTrace :: State -> [Event] -> Maybe (State, Trace)
runTrace = go []
where
go acc s [] = Just (s, reverse acc)
go acc s (e:es) = case transition s e of
Just s' -> go ((s, e):acc) s' es
Nothing -> Nothing
```
まとめ
| **圏論概念** | **Haskellでの対応** |
| ----------- | ------------------------------------------- |
| 対象（object） | `State`（データ型） |
| 射（morphism） | `Event` + `transition :: s -> e -> Maybe s` |
| 合成 | `foldl` と `>>=` による逐次適用 |
| 恒等射 | 自明な `id :: State -> State`（何も起こらない） |
| 合成可能性 | `Maybe` でモナディックに検証 |
| 圏 | 明示的に定義しなくても、実装が圏論的意味論に従っている |
UI の画面遷移を「状態＝画面」「操作＝射（イベント）」として圏論的にモデル化することもできる。