什麼是free structure?

01-08

在Data type a la carte中，我看到了這句話：
「In general, a structure is called free when it is left-adjoint to a forgetful functor.」
left adjoint完全不明白，是什麼？
forgetful functor明白了一點，但是wikipedia, mathworld, nlab上都沒看到足夠的例子。。。有人能舉幾個例子嗎？
另外順帶球個faithful functor的例子

溫馨提示：為確保閱讀體驗請在電腦上用瀏覽器閱讀。

基本更新完成，歡迎@霧雨魔理沙@閱千人而惜知己@祖與占@彭飛評論。

謝邀，Free Structure是一個牽扯很多基礎概念的東西，先簡單的說一下吧。

Free是什麼，用人話來說就是自由自在，自然而然。再具體一點就是：Free Structure就是依其自性自由自在的構造了一個自然而然呈現的結構。

Free Structure是由較簡單的類型通過簡單而自然的方法構造得到的，具體如下：

1. Free Structure擁有類型F，其基於的基底類型是X，還有額外的Free Structure的運算。

2. 定義一個嵌入函數ins: X -&> F，該函數將類型X的值通過簡單而自然的方法變為(injection)類型F的值。

3. Free Structure的類型F只包含由嵌入函數ins得到的值，和由這些值通過Free Structure的運算得到的值。既沒有多餘的值，也沒有少必要的值，恰到好處。

4. Free Structure的運算規則適用於類型F的所有這些值，類型F包含的所有值滿足Free Structure的定義和運算規則。

我們可以將Free看成一個類型構造，其將類型X構造成Free Structure的類型F，類型X的值的集合是該Free Structure的生成集。下面這張圖解釋了Free的構造過程。以Monoid為例，類型F和類型G都是基於類型X的Monoid，其中類型F是Free Structure，一般也稱為FreeMonoid，是基於類型X的所有Monoid中最好的一個候選，是所有基於類型X的Monoid組成的範疇Mon的初始對象(initial object)。所有其它的Monoid都可以從FreeMonoid得到，都有一個唯一的從FreeMonoid到其它Monoid的同態態射(monoid homomorphism)，FreeMonoid在同構上來說是唯一的。也就是說，我們有一個ins的函數，類型X到類型F的一個注入函數，如果對任一個從類型X到G的函數f，則有唯一的函數free f，可以從類型F得到類型G。函數free f也可稱為求值函數，將類型F的數據結構求值為類型G的值。在Haskell的List中，free就是我們熟悉的fold，List就是FreeMonoid（在有限元素的情況下）。

只要滿足上面這個圖的交換條件，我們就找到了一種Free Structure。除了Monoid外，還有Applicative、Monad、Arrow等都可以通過Free構造得到Free Structure，具體的Free Structure有Free Monoid, Free Applicative, Free Monad, Free Arrow等。下面我將介紹前面三種Free Structure。FreeMonoid是Monoid的Free Structure，是範疇Mon的初始對象(initial object)，將類型x變為Monoid，類型x是FreeMonoid的生成集。Freemonoid的例子有List（有限元素情況下）、包括0的自然數、字元串的A*等。在Haskell中，Monoid的定義如下：

class Monoid m where empty :: m mappend :: m -&> m -&> m

那麼FreeMonoid是如何構造的呢？很簡單，以List為例，先給出List的定義，再增加List對應的Monoid的運算，即定義單位元(mempty)和乘法操作(mappend)，實現了Monoid的一個實例。然後定義ins函數，從類型x中得到類型[x]。最後定義free函數，得到free f將類型[x]的值變換為任意一個其它Monoid類型b的值，這樣我們就得到了類型為[a]的一個FreeMonoid。具體過程如下：

data [x] = [] | x : [x] -- this is pseudo code


instance Monoid [x] where

  mempty = []

  mappend = (++)
ins :: x -&> [x]

ins x = [x]

free f :: Monoid b =&> (x -&> b) -&> [x] -&> b -- free f = foldr (x b -&> f x `mappend` b) mempty free f [] = mempty free f (x:xs) = f x `mappend` free f xs

FreeMonad是Monad的Free Structure，是所有Monad組成的範疇的初始對象(initial object)，FreeMonad將任意自函子f變為Monad，自函子f是FreeMonad的生成集。FreeMonoid能夠用於最簡單的DSL語言，但這些DSL語言的元語只能線性的串起來，且不能上下文相關。當我們需要具有分支和循環的表示並且上下文相關時，就要用到FreeMonad了。我們知道Monad是自函子範疇上的Monoid，因此FreeMonad和FreeMonoid有類似的結構，可以按如下方式定義FreeMonad。

class Applicative m =&> Monad m where return :: a -&> m a join :: m (m a) -&> m a


data Free f a = Pure a | Free (f (Free f a))
instance Functor f =&> Monad (Free f) where

  return = Pure

  join (Pure a) = a

  join (Free fa) = Free (fmap join fa)
ins :: (Functor f) =&> f a -&> Free f a

ins fa = Free (fmap Pure fa)

free :: (Functor f, Monad g) =&> (forall a. f a -&> g a) -&> (forall a. Free f a -&> g a) free f (Pure a) = return a free f (Free fa) = join (f (fmap (free f) fa))

FreeApplicative是Applicative的Free Structure，是所有Applicative組成的範疇的初始對象(initial object)，FreeApplicative將任意自函子f變為Applicative，自函子f是FreeApplicative的生成集。當我們的DSL語言的元語不需要上下文相關時，使用FreeApplicative就可以了，性能會更高。同樣的，Applicative也是自函子範疇上的Monoid，只是自函子的張量積和Monad的不同。因此FreeApplicative和FreeMonoid也有類似的結構，可以按如下方式定義FreeApplicative。

class Functor f =&> Applicative f where pure :: a -&> f a (&<*&>) :: f (a -&> b) -&> f a -&> f b


-- define this for express monoid of endofunctor

class Functor f =&> Monoidal f where

  unit :: f ()

  (**) :: f a -&> f b -&> f (a, b)
infixr 4 :$:

data FreeA f a = Pure a | forall b. f (b -&> a) :$: FreeA f b
instance Functor f =&> Applicative (FreeA f) where

  return = Pure

  Pure g &<*&> y = fmap g y

  (h :$: as) &<*&> y = fmap uncurry h :$: ((,) &<$&> as &<*&> y)
ins :: (Functor f) =&> f a -&> FreeA f a

ins fa = fmap const fa :$: Pure ()

free :: (Functor f, Applicative g) =&> (forall a. f a -&> g a) -&> (forall a. FreeA f a -&> g a) free f (Pure a) = pure a free f (h :$: as) = f h &<*&> free f as

從上面FreeMonoid、FreeApplicative和FreeMonad這三個例子我們可以看到，其實現有很高的相似性，這是因為這三種數據類型都具有Monoid這個結構，只是基底類型和單位元、乘法不一樣，因此具有同樣的形式 μX . I + A ? X。也即這三種數據類型是函子I +A ? ?的不動點，其具有類似的形式，我們再看一下這三種數據類型的定義，其形式很具有一致性。

X = I + A ? X data [x] = [] | x : [x] data FreeA f a = Pure a | forall b. f (b -&> a) :$: FreeA f b data Free f a = Pure a | Free (f (Free f a))

遺忘函子(forgetful functor)和Free相反，其將Free Structure的類型F變換為其基底類型X。簡單的例子就是F-Alg範疇中的forgetful functor其形式為U ∶ F-Alg(C) → C，其作用是將F-Alg中額外的信息都遺忘掉，只剩下範疇C中的信息，定義為U ?A, a? = A 和U h = h，這裡 ?A, a? 是F-Alg(C)的對象。Free和遺忘函子U組成一對伴隨函子，Free是左伴隨，U是右伴隨，記為Free -| U。因此我們有Hom_F-Alg(Free A, B) ? HomC(A, U B)，Free和U的伴隨關係如下圖所示。

伴隨(adjunction)是範疇論中的一個基本而又重要的概念，幾乎所有的數學對象都可以由伴隨來得到。伴隨包括伴隨函子(adjoint functor)和伴隨函數(adjunction function)，這是一對互相反著運動的相生相伴的系統。下面這張伴隨圖簡明扼要的描述了伴隨的關係。

那麼伴隨究竟是什麼呢，讓我們緩緩道來。當我們有兩個函子F : D -&> C和G : C -&> D，如果如下的條件成立，則我們就說F和G是一對伴隨函子，並稱F是G的左伴隨函子。

phiL: HomC(F d, c) ? HomD(d, G c) :phiR

ε : F ° G -&> Id η : Id -&> G ° F

上面的phiL和phiR是一對自然同構，phiL將HomC(F d, c)中的函數變為HomD(d, G c)中的函數，phiR則相反。f和g是一對伴隨函數，f是左伴隨函數，g是右伴隨函數。η和ε是一對自然變換，η是所有函數g的unit，ε是所有函數f的counit。可以看到，伴隨中的一切都是一陰一陽，相生相伴，陰陽相互變化的。

那麼伴隨中的陰陽是如何變化的呢，其符合如下這些規律:

phiL f = g === f = phiR g


f = ε ° phiR g

g = phiL f ° η
f = ε . phiR (phiL f)

g = phiL (phiR g) . η
phiL id = η

phiR id = ε

id = εF ° Fη --- F --Fη--&> F°G°F --εF--&> F id = Gε ° ηG --- G --ηG--&> G°F°G --Gε--&> G

在Haskell中可以很好的表示伴隨函子的概念，一個很常見的例子是函子((,) a)和((-&>) a)組成的一對伴隨函子，下面的counit和unit分別是ε和η，unit是Monad的return函數，counit是Comonad的extract函數，具體如下所示：

class (Functor f, Functor g) =&> Adjoint f g where counit :: (f (g a)) -&> a unit :: a -&> (g (f a))


phiL :: (Adjoint f g) =&> (f a -&> b) -&> (a -&> g b)

phiL f = fmap f . unit
phiR :: (Adjoint f g) =&> (a -&> g b) -&> (f a -&> b)

phiR f = counit . fmap f
instance Adjoint ((,) a) ((-&>) a) where

  -- counit :: (a, a -&> b) -&> b

  counit (a, f) = f a

-- unit :: b -&> (a -&> (a, b)) unit b = a -&> (a, b)

眼尖的同學可能會發現上面的unit函數返回了一個類似State s的數據類型，如果我們按如下方式定義StateA，則可以得到一個StateA s的Monad。

-- Compose ((-&>) s) ((,) s) newtype StateA s a = StateA { runStateA :: s -&> (s, a) }

instance Monad (StateA s) where return a = StateA $ s -&> (s, a) --- unit b = a -&> (a, b) join (StateA st) = StateA $ s -&> let (s", t) = st s in t s"

上面的StateA的s -&> (s, a)可以看成是函子((-&>) s)和((,) s)的組合，即Compose ((-&>) s) ((,) s)。更一般化的，若我們有F和G兩個伴隨函子，其中F是左伴隨函子，則通過函子的組合我們可以得到一個Monad，即Compose G F是一個Monad，具體如下所示：

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- f is left adjoint functor of g instance Adjoint f g =&> Monad (Compose g f) where return a = Compose $ unit a join m = Compose . fmap counit . getCompose $ fmap getCompose m

在Haskell中很常用和普通的兩個函數curry和uncurry，就是一對伴隨函子的自然同構phiL和phiR。實際上這對伴隨函子就是(, a)（很可惜Haskell的類型系統無法直觀表示這種形式）和((-&>) a)。函子((-&>) s)和(, s)的組合就是我們經常用到的State s這個Monad，其unit函數是(,)，也即coeval函數，counit函數是uncurry ($)，也即eval函數，具體如下所示：

-- curry: Hom((a, b), c) = Hom(a, c^b) :uncurry curry :: ((a, b) -&> c) -&> a -&> b -&> c uncurry :: (a -&> b -&> c) -&> (a, b) -&> c


-- Compose ((-&>) s) (, s)

newtype State s a = State { runState :: s -&> (a, s) }
-- Adjoint (, s) ((-&>) s)

-- phiL id = curry id = η

-- phiR id = uncurry id = ε

unit   =     (,)     = curry id   = coeval :: a -&> b -&> (a, b)

counit = uncurry ($) = uncurry id = eval :: (b -&> a, b) -&> a

instance Monad (State s) where return a = State $ s -&> (a, s) --- unit a = -&> (a, b) join (State st) = State $ s -&> let (t, s") = st s in t s"

可以看到State和StateA這兩個數據類型非常相似，其區別就在於(a, s)和(s, a)這個交換。實際上在Haskell的類型系統中(a, s)和(s, a)是同構的，因此State和StateA是同構的。

我們很熟悉的兩種數據類型Product和Coproduct，也可以用伴隨函子來表示，而且很好的呈現了Product和Coproduct的對偶關係。在Haskell中Product a b類型就是(a, b)，Coproduct a b類型就是Either a b。我們再引入? ∶ C → C × C這個Diagonal Functor，其定義為?A = ?A, A? 和?f = ?f ,f ?。那麼Either和(,)這兩個Bifunctor和Δ 這個Diagonal Functor就一起組成了伴隨三角，表示為Either ? Δ ? (,)，使得類型(a, b)和類型Either a b互相對偶。將Either記為+和(,)記為x，則如下圖所示。

因Haskell的類型系統中沒有product kind，無法表示乘積範疇 C × C，故上圖無法用Haskell的代碼來表示，大家只好腦補了。

最後，我們來看看最重要的米田引理和伴隨函子之間的關係。米田引理的定義如下：

上面的米田引理定義誘導出了一對伴隨函子(adjoint functor) ，左伴隨函子(A ? ?) 和右伴隨函子Hom(A, ?)，從而如下的同構形式成立：

Hom(Cop?C, Set)?Hom(C, Hom(Cop, Set))

更具體的描述請看米田引理的在編程中的實際應用？ - parker liu 的回答。

fully faithful的函子F引導的如下函數Fx,y是一個雙射函數，誘導出一個嵌入關係。

一個重要的例子就是米田嵌入函子Y，該函子將任意一個local small category範疇C嵌入到範疇Fun(Cop, Set)。我們再次應用米田嵌入，可以得到高階函子範疇Fun(Fun(Cop, Set), Set)，多次應用，則可以得到更高階到函子範疇。

伴隨函子描述了一個事物的兩個方面，即一陰一陽。這兩個方面的變化是相互關聯又互相反向運動的，很像太極圖中的陰陽變化之道。

在編程實踐方面，我們往往會遇到靈活和高效這對矛盾，即能夠靈活組合的程序往往是低效運行的，而高效運行的程序往往又是難以組合的。如何解決這對矛盾呢，伴隨函子給了我們一個可能的方向，我們可以在一個範疇中實現可以靈活組合的形式，另一個範疇中實現高效運行的形式，利用伴隨函子來將靈活組合的形式轉換為高效運行的形式。具體如何做呢，米田引理和丘奇表示(Church representation)給了我們一些啟示。

參考鏈接：

Free structure

Free Monoids

Definition Let A and B be categories. If F : A → B and U : B

→ A are functors, we say that F is left adjoint to U and U is right

adjoint to F provided there is a natural transformation η : id → UF such

that for any objects A of A and B of B and any arrow f : A → UB, there

is a unique arrow g : FA → B such that

commutes.

記為F ? U （F為U的左伴隨， U為F的右伴隨, UF是 U
? F的縮寫）

Free Monoid就是free structure的例子

恆等函子是 faithful functor的例子（逃我只是個搬運工

Ref: http://www.math.mcgill.ca/triples/Barr-Wells-ctcs.pdf

--------------------------------------

在研究monad和comand的關係時，看過adjoint

伴隨可視為isomorphism between arrows，把? 記為Adjunction

trait Adjunction[F[_],G[_]] { //F is left adjoint to G def left[A,B](f: F[A] =&> B): A =&> G[B] def right[A,B](f: A =&> G[B]): F[A] =&> B }

Composing adjoint functors 可以形成 monad和comonad

我從free algebra的角度來答一下吧，

free monad只是free algebra中的一種，還有很多free algebra的例子，

例如，free monoid，free group，free ring等等。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

free algebra與forgetful functor和left adjoint有關：

For each type $au$ of algebras, we have the category $Alg_ au$ of all algebras of the given type, the forgetful functor $G:Alg_ au ightarrow Set$ , and its left adjoint $F$ , which assigns to each set $S$ the free algebra $FS$ of type $au$ generated by elements of $S$ .

——《Categories for the Working Mathematician 2nd - P137》

我們看到，一個有結構的範疇 $Alg_ au$ ，通過forgetful functor損失了一些結構，映射成了另外一個範疇 $Set$ 。一個直觀的想法就是，我們能否把 $Set$ 再映射回來 $Set ightarrow Alg_ au$ 。

這不太容易，因為forgetful functor已經損失了一些結構。但是我們可以通過類似「求極值」的方式，找到一個最簡復原方式。那就是通過forgetful functor的left adjoint來完成，因為forgetful functor的left adjoint剛好是一個從 $Set$ 到 $Alg_ au$ 的函子。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

1. 什麼是類型為 $au$ 的代數

在universal algebra中，一個algebra由一個集合 $A$ 以及集合上的一系列運算構成。

集合 $A$ 上的 $n$ 元運算是一個函數，它將 $A$ 中的 $n$ 個元素，映射為一個元素，

代數中所有運算的集合記為 $au$ ，我們稱該代數是一個 $au$ 類型的代數。

所有類型為 $au$ 的代數，構成了一個範疇 $Alg_ au$ ，

它的對象為某一個類型為 $au$ 的代數，箭頭為代數之間的代數同態。

2. 什麼是forgetful functor

一個函子可能會「遺忘」範疇中的部分（或全部）結構，這樣的函子稱為forgetful functor。

例如，forgetful functor $U:Grp ightarrow Set$ ，將範疇 $Grp$ 中的每一個群 $g$ ，映射為一個由群 $g$ 的所有元素組成的集合 $Ug$ ，（「遺忘」了建立在群乘法之上的群結構，）並且將範疇 $Grp$ 中的任意兩個群之間的群同態，映射為兩個集合之間的函數。

3. 什麼是left adjoint

要理解left adjoint的概念比較麻煩，下面我們要分以下幾個概念來分別介紹，

comma category，coslice category，initial object，initial morphism，adjoint functor。

3.1 comma category

給定範疇 $E,C,D$ 和函子 $T,S$ ，

$Eoverset{T}{ ightarrow}Coverset{S}{leftarrow}D$

我們構造comma category，記為 $(Tdownarrow S)$ ，它由以下對象和箭頭組成：

$(Tdownarrow S)$ 範疇的對象為三元組 $leftlangle e,d,f ight angle$ ，其中， $e$ 是範疇 $E$ 中的對象，d是範疇 $D$ 中的對象， $f:Te ightarrow Sd$ 是範疇 $C$ 中的箭頭。

$(Tdownarrow S)$ 範疇的箭頭為二元組 $leftlangle k,h ight angle:leftlangle e,d,f ight angle ightarrowleftlangle e^prime,d^prime,f^prime ight angle$ ，其中， $k:e ightarrow e^prime$ ， $h:d ightarrow d^prime$ ，並且滿足， $f^primecirc Tk=Shcirc f$ 。

3.2 coslice category

給定範疇 $E,C,D$ 和函子 $T,S$ ，

$Eoverset{T}{ ightarrow}Coverset{S}{leftarrow}D$

取 $C$ 中的某個元素 $c_0$ ，它唯一對應一個函子 $T:1 ightarrow C$ ，

在這種情況下comma category $(Tdownarrow S)$ ，就可以記為 $(c_0downarrow S)$ ，稱為coslice category。

coslice category $(c_0downarrow S)$ 的對象是 $leftlangle d,f ight angle$ ，其中， $d$ 是 $D$ 中的對象， $f:c_0 ightarrow Sd$ 是 $C$ 中的箭頭。

coslice category $(c_0downarrow S)$ 的箭頭是 $h:leftlangle d,f ight angle ightarrowleftlangle d^prime,f^prime ight angle$ ，其中 $h:d ightarrow d^prime$ ，並且滿足， $f^prime=Shcirc f$ 。

3.3 initial object

設 $C$ 是一個範疇， $c$ 是它的一個對象，如果對於 $C$ 中的任意對象 $x$ ，存在唯一的箭頭 $c ightarrow x$ ，就稱 $c$ 是範疇 $C$ 的initial object。

3.4 initial morphism

設 $D,C$ 是範疇， $U:D ightarrow C$ 是函子， $c$ 是範疇 $C$ 中的一個對象，

根據initial object的定義，coslice category $(cdownarrow U)$ 的initial object $leftlangle d,f ight angle$ 滿足以下條件，

對於coslice category $(cdownarrow U)$ 中的任意對象 $leftlangle d^prime,f^prime ight angle$ ，存在唯一的箭頭， $h:d ightarrow d^prime$ ，使得 $f^prime=Uhcirc f$ 。

這個initial object $leftlangle d,f ight angle$ ，稱為從對象 $c$ 到函子 $U$ 的initial morphism。

（注意，這裡是從對象到函子，沒寫錯，指的是coslice category $(cdownarrow U)$ 。）

3.5 adjoint functor

設 $D,C$ 是範疇， $U:D ightarrow C$ 是函子， $c_1,c_2$ 是範疇 $C$ 中的對象，

$leftlangle d_1,f_1 ight angle$ 是從對象 $c_1$ 到函子 $U$ 的initial morphism，其中 $f_1:c_1 ightarrow U(d_1)$ 。

$leftlangle d_2,f_2 ight angle$ 是從對象 $c_2$ 到函子 $U$ 的initial morphism，其中 $f_2:c_2 ightarrow U(d_2)$ 。

根據initial morphism的性質，對於 $C$ 中的箭頭 $h:c_1 ightarrow c_2$ ，存在 $D$ 中唯一的箭頭 $g:d_1 ightarrow d_2$ ，使得 $f_2circ h=Ugcirc f_1$ 。

因此，我們找到了一個從範疇 $C$ 到 $D$ 的對應關係。

我們把範疇 $C$ 中的對象 $c_1,c_2$ ，分別對應到了範疇 $D$ 的對象 $d_1,d_2$ 上，

把範疇 $C$ 中的箭頭 $h:c_1 ightarrow c_2$ ，對應到了範疇 $D$ 的箭頭 $g:d_1 ightarrow d_2$ 上。

如果對於範疇 $C$ 中任意的對象和箭頭，都能滿足這個條件，

我們就找到了一個從範疇 $C$ 到範疇 $D$ 的函子， $F:C ightarrow D$ ，

$F$ 稱為 $U$ 的left adjoint， $U$ 稱為 $F$ 的right adjoint，記為 $Fdashv U$ 。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

以上我們介紹了範疇 $Alg_ au$ ，forgetful functor和left adjoint，現在我們就可以理解free algebra的概念了。

free algebra，就是forgetful functor $Forget:Alg_ au ightarrow Set$ 的left adjoint $Free:Set ightarrow Alg_ au$ ，作用在範疇 $Set$ 的對象 $s$ 上之後，得到的一個類型為 $au$ 的代數 $Free(s)$ 。

其中 $s$ 稱為代數 $Free(s)$ 的生成集（generator）， $Free(s)$ 稱為由 $s$ 生成的代數。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

4. 我們補充一下free monoid的概念（2017.07.09）

4.1 Kleene closure

集合 $V$ 的Kleene closure定義如下，

$V^*=cup_{iin N}V_i=V_0cup V_1cup V_2cupcdots$

其中， $V_0={epsilon}$ ， $V_1=V$ ， $V_{i+1}={uv|uin V_i,vin V}$ ，

$V^*$ 中的元素稱為string， $V_{i+1}$ 定義中的 $uv$ 將兩個string $u$ 和 $v$ 連接到了一起，稱為string concatenation，不妨記為「 $cdot$ 」。

4.2 free monoid

可以證明， $V^*$ 連同string concatenation運算，是一個由 $V$ 生成的free monoid $(V^*,cdot)$ ，

即證明 $leftlangle V^*,f ight angle$ 是coslice category $(Vdownarrow U)$ 的initial object，其中 $f:V ightarrow V^*$ 。

Why is the free monoid free?

4.3 generator

其實剛才的描述不太嚴謹，因為free algebra還與forgetful functor的定義有關，

我們還需補充以下定義，定義forgetful functor為 $U:Mon ightarrow Set$ ， $Mon$ 是所有monoid構成的範疇， $Set$ 是所有集合構成的範疇。forgetful functor將 $Mon$ 中一個具體的monoid $(M,cdot)$ ，映射為它的群元素之集合 $M$ ，將該monoid與其他monoid之間的群同態，映射為集合之間的函數。

因此，forgetful functor $U$ 將monoid $(V^*,cdot)$ 映射為集合 $V^*$ ，它left adjoint $Free:Set ightarrow Mon$ ，將 $V$ 映射為由 $V$ 生成的free monoid $(V^*,cdot)$ 。

注意，forgetful functor將 $(V^*,cdot)$ 映射為 $V^*$ ，而不是 $V$ ，free monoid $(V^*,cdot)$ 是由 $V$ 生成的，而不是 $V^*$ 。

設 $f:V ightarrow V^*$ ， $(X,cdot)$ 是任意的一個monoid，則映射 $h:V ightarrow X$ ，確定了唯一的群同態 $g:V^* ightarrow X$ ，使得 $h=gcirc f$ ，因此， $leftlangle V^*,f ight angle$ 是從 $V$ 到 $U$ 的initial morphism， $(V^*,cdot)$ 是由 $V$ 生成的free monoid。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

參考：

1. Categories for the Working Mathematician 2nd

2. Category theory for computer science

3. A Course in Universal Algebra

4. Wikipedia: Universal Algebra

5. Wikipedia: Forgetful functor

6. Wikipedia: Initial and terminal objects

7. Wikipedia: Comma Category

8. Wikipedia: Universal Property

9. Wikipedia: Adjoint Functor

10. Wikipedia: Free Object

11. Wikipedia: Free Algebra

12. Stack Exchange: Why is the free monoid free

forgetful functor 是可遺函子吧。。。

（翻出範疇論筆記）

$F : obj( extbf{Grp}) o obj( extbf{Set})$

$(A, o) mapsto F(A) = A$

這種感覺。。。

伴隨函子就不是很清楚了。。。我去問問老師（

首先，所有 set 的範疇是 Set，所有 monoid 的範疇是 Mon。顯然每個 monoid 都有一個 underlying set，這個「脫」的過程可以看作一個 forgetful functor，叫 U : Mon -&> Set。List 這個結構可以從一個 set 構建一個 monoid，免費穿上了 monodic structure，可以看作另一個 functor，List : Set -&> Mon。這兩個 functor 顯然是對稱的，那他們是不是互為 left/right adjoint 呢？

如果是，需要有這麼一個 natural isomorphism：對任意 s in Set 和任意 m in Mon，List s -&> m ? s -&> U m。left/right adjoint 指示 functor 出現在左側還是右側。

哎~如果寫成 adjunction 的另一種表示方式 unit η 和 counit ε ：

η : Id -&> U ° List

ε : List ° U -&> Id

其中 Id 為 identity functor。可見 U 和 List 的互為 inverse 關係。