Hask圏とファンクター - Blog | まさとも Official Website

はじめに

Haskellは，純粋関数型言語と呼ばれるプログラミング言語で，数学的な関数を主体としています．PythonやCのようなプログラミング言語でももちろん関数はありますが，純粋関数型言語の関数は「値を受け取り，返す」だけを行います．文字の出力やネットワーク接続などの副作用は持ちません．なぜなら，それは数学的な関数の関心ごとではないからです．

関数型言語については，次の記事がわかりやすかったので，紹介させていただきます．

関数型言語の「関数」 | 関数型言語とは何か？(Haskellで学ぶ)

そんなHaskellなので，数学，特に圏論という分野ととても相性が良いです．というか，圏論の概念を持ち込んでいます．今回は，数学的な話をやんわりと含めながら，Haskellの主要な概念であるHask圏とファンクターについて解説していこうと思います．

Haskell記法の説明

記事中でHaskellのコードが登場するので，最小限の記法を説明しておきます．

型シグネチャと関数定義: 関数の型を::で宣言し、続けて定義を書く

length :: [a] -> Int           -- 型シグネチャ: 任意の型aのリストを受け取り，Intを返す
length [] = 0                  -- 関数定義: 空のリストに対しては0を返す
length (x:xs) = 1 + length xs  -- 関数定義: リストを要素xとその後のリストxsに分けて，xsに再起的にlengthを適用させる

increment :: Int -> Int -- 型シグネチャ
increment x = x + 1     -- 関数定義

関数合成: (.)演算子で関数を合成

(.) :: (b -> c) -> (a -> b) -> a -> c
g . f  -- 「fを適用してからgを適用」を意味する

データ型: dataキーワードで新しい型を定義

data Bool = True | False     -- Bool型の定義
data [a] = [] | a : [a]      -- リスト型の定義（簡略化）

型クラス: classで型に共通の操作を定義し、instanceで具体的な実装を提供

class Eq a where             -- Eq型クラスの定義（等値比較）
  (==) :: a -> a -> Bool

instance Eq Bool where       -- Bool型をEqのインスタンスとして実装
  True == True = True
  False == False = True
  _ == _ = False

圏論の基礎とHask圏

圏

圏は対象(Object)と射(arrow/morphism)からなる，数学的な構造を扱うための枠組みです．少し雑に説明してみます．

要素

対象: 興味の対象．例えば，集合，数，群，データ型，いろいろなものがありうる．
射: 対象から対象への関係性．例えば，集合の圏なら，実数集合から実数集合への関数などがこれに当たります．ただし，関数の形をしている必要はなく，大小関係なども射になり得ます．

満たすべき条件

合成: 対象 $A$ から $B$ への射 $f$ と $B$ から $C$ への対象 $g$ があれば， $A$ から $C$ への合成射 $g \circ f$ が存在する
結合: $h \circ (g \circ f)=(h \circ g) \circ f$ が成り立つ．つまり，どの順番で合成しても結果は変わらない．
恒等射: どんな対象 $A$ にも，それ自身への射 $id_A$ が存在する．「何もしない」関係性や変換．

合成や結合は中学とか高校数学でやりましたね．かなり当たり前に思える性質です．つまり圏とは，数学的な構造が満たしていて欲しい最小限のルールだけを課したものだとも言えます．

Hask圏の定義

Hask圏は，Haskellの型システムを圏論的に捉えたものです．上の定義に従って，説明していきます．まず，対象と射は以下のとおりです．

対象: Haskellの型（Int, String, Bool, [Int]など）
射: 型から型への関数（Int -> String, [a] -> Intなど）

例えば，length :: [a] -> Intという関数は，リスト型[a]からInt型への射として扱われます．同様に，インクリメントや，否定not :: Bool -> Boolなども，それぞれ対応する型間の射になります．

Hask圏が満たすべき条件も確認してみましょう：

合成: Haskellの関数合成演算子(.)がこれに対応します．

-- f :: a -> b, g :: b -> c があるとき
-- g . f :: a -> c が存在する
(g . f) x = g (f x)

-- 具体例: インクリメントしてから文字列に変換
increment :: Int -> Int
increment = (+1)

-- show関数: 値を文字列に変換するHaskellの標準関数
show :: Int -> String

-- 合成: Int -> String
incrementThenShow :: Int -> String
incrementThenShow = show . increment
-- incrementThenShow 5 = "6"

結合律: 関数合成は結合律を満たします．

h . (g . f) = (h . g) . f

恒等射: 恒等関数idが各型の恒等射として働きます．

id :: a -> a
id x = x

このように，Haskellの関数と型システムは自然に圏を形成していることがわかります．

ファンクター

圏論におけるファンクター（関手）

ファンクターは，圏から圏への「構造を保存する写像」です．圏 $\mathcal{C}$ から圏 $\mathcal{D}$ へのファンクター $F$ は以下を満たします．

対象の対応: $\mathcal{C}$ の各対象 $A$ を $\mathcal{D}$ の対象 $F(A)$ に対応させる
射の対応: $\mathcal{C}$ の各射 $f: A \to B$ を $\mathcal{D}$ の射 $F(f): F(A) \to F(B)$ に対応させる

そして，構造の保存として以下を満たす必要があります：

恒等射の保存: $F(id_A) = id_{F(A)}$
合成の保存: $F(g \circ f) = F(g) \circ F(f)$

HaskellのFunctor

Haskellにおいて，ファンクターは型クラス（型に対して特定の操作を定義するインターフェース）として実装されています．

Data.Functor

class Functor f where
  fmap :: (a -> b) -> f a -> f b

fmapの型シグネチャは次のとおりです．

(a -> b): Hask圏の射（関数）
f a -> f b: 射を「持ち上げた」もの

つまり，fmapは関数a -> bを，コンテナに包まれた関数f a -> f bに変換する操作です．これは数学的ファンクターの「射の対応」そのものです．型（対象）の対応は言わずもがなですね．

一番単純な例としては，リストをFunctorのインスタンスとして定義することができます．

instance Functor [] where
  fmap = map

対象の対応: 型aを[a]に対応させる

射の対応: 関数a -> bを[a] -> [b]に対応させる

-- fmapで持ち上げられたshow関数  
fmap show :: [Int] -> [String]

fmap show [1, 2, 3] = ["1", "2", "3"]

ファンクター則の検証

Haskellのファンクターは，数学的ファンクターの性質を満たす必要があります．

恒等律

fmap id = id

恒等関数idをfmapで持ち上げても，結果は恒等関数のままです．

リストでの例:

fmap id [1, 2, 3] = [1, 2, 3] = id [1, 2, 3]
-- 実際に map id [1, 2, 3] = [1, 2, 3]

結合律

fmap (g . f) = fmap g . fmap f

関数を合成してからfmapするのと，それぞれをfmapしてから合成するのは同じ結果になります．

リストでの例

-- 関数の定義
double :: Int -> Int
double x = x * 2

-- 左辺: 合成してからfmap
fmap (show . double) [1, 2, 3] = ["2", "4", "6"]

-- 右辺: それぞれfmapしてから合成
(fmap show . fmap double) [1, 2, 3] = fmap show [2, 4, 6] = ["2", "4", "6"]

ここまで見たとおり，ファンクターは，構造を維持しながら関数を適用させられることがわかります．

感想

今回は，Hask圏とファンクターについて，数学的背景とHaskellでの実装を関連付けながら見てきました．自分は大学で数学を学んでいたのでHaskellそれ自体に魅力を感じていますが，数学でもプログラミングでも「抽象」は1つのキーワードだと思うので，他の畑の方も学ぶ価値はあるのかなと思っています．自分も勉強し始めたばかりですが…．

Haskellには他にも，アプリカティブファンクターやモナドなど，圏論に基づく概念が多数あります．これについてもそのうち書けたらなと思っています．