2-Tuple と Functor

まず、Functor とは以下の性質を満たすものでした：

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

-- 恒等関数の保存
fmap id == id

-- 合成関数の分配
fmap (f . g) == fmap f . fmap g

ここで、Haskell においては 2-Tuple も Functor のインスタンスであり：

instance Functor ((,) a) where
    fmap f (x, y) = (x, f y)

上記の要領で定義されます。すなわち、fmap において第 2 要素に対してのみ関数を適用する処理になります。

なぜこのような実装になるのでしょうか？

まず、2-Tuple を構成する (a, b) という記述を、 (,) なる演算子に型を 2 つ作用させるとみなします。すなわち、この演算子の種は * -> * -> * となります。(実際、GHCi などでこれを確認することができます。)

ここで、 (,) a と型を部分適用すると、この種は * -> * となり、Functor の種と一致します。この状態で fmap の性質に適合するような実装を行うと、先の定義が得られます。

この実装が Functor としての性質を満たすことも、以下のように確かめられます：

fmap id (x, y)
== (x, id y)
== (x, y)
== id (x, y)
-- ==> fmap id == id

fmap (f . g) (x, y)
== (x, (f . g) y)
== (x, f (g y))
== fmap f (x, g y)
== fmap f (fmap g (x, y))
== (fmap f . fmap g) (x, y)
-- ==> fmap (f . g) == fmap f . fmap g

また同様な流れで、N-Tuple に対しても Functor を定義可能です。

2-Tuple と Applicative

まず、Applicative とは以下の性質を満たすものでした：

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

-- 恒等関数の保存
pure id <*> ax == ax

-- 分配律
pure (.) <*> af <*> ag <*> ax == af <*> (ag <*> ax)

-- 準同型写像
pure f <*> pure x == pure (f x)

-- 交換律
af <*> pure x == pure ($ x) <*> af

ここで、Haskell においては 2-Tuple も Applicative のインスタンスであり：

instance Monoid a => Applicative ((,) a) where
    pure x = (mempty, x)
    (u, f) <*> (v, x) = (u <> v, f x)

上記の要領で定義されます。すなわち、第 2 要素に対してのみ関数を適用する処理に加えて、第 1 要素が Monoid であることを要請します。

なぜこのような実装になるのでしょうか？

まず、Functor 同様 Applicative の種も * -> * ですから、2-Tuple を Applicative のインスタンスにする場合、依然として f = ((,) a) に関して考える必要があります。さて、この場合の pure :: a -> f a は pure x = (?, x) となりますが、第 1 要素には何を割り当てるのが適切でしょうか？

これがまさに、第 1 要素が Monoid であることを要請している理由です。? はある種のデフォルト値であることを期待しますが、任意の型に対して適切なデフォルト値を一意に決めることはできません。

そこで、デフォルト値を単位元にすることを考えます。すると、単位元が存在する数学的な構造は Monoid にほかならないので、第 1 要素に関して Monoid であることが要請されるのです。また Monoid であれば、Applicative としての連鎖を行う際に、適切に第 1 要素を連結していくことが可能です。

この実装が Applicative としての性質を満たすことも、以下のように確かめられます：

pure id <*> (m, x)
== (e, id) <*> (m, x)
== (e <> m, id x)
== (m, x)
-- ==> pure id <*> ax == ax

pure (.) <*> (m0, f) <*> (m1, g) <*> (m2, x)
== (e, (.)) <*> (m0, f) <*> (m1, g) <*> (m2, x)
== (e <> m0, (.) f) <*> (m1, g) <*> (m2, x)
== (e <> m0 <> m1, (.) f g) <*> (m2, x)
== (e <> m0 <> m1 <> m2, (f . g) x)
== (m0 <> (m1 <> m2), f (g x))
== (m0, f) <*> (m1 <> m2, g x)
== (m0, f) <*> ((m1, g) <*> (m2, x))
-- ==> pure (.) <*> af <*> ag <*> ax == af <*> (ag <*> ax)

pure f <*> pure x
== (e, f) <*> (e, x)
== (e <> e, f x)
== (e, f x)
== pure (f x)
-- ==> pure f <*> pure x == pure (f x)

(m, f) <*> pure x
== (m, f) <*> (e, x)
== (m <> e, f x)
== (e <> m, f $ x)
== (e <> m, ($ x) f)
== (e, ($ x)) <*> (m, f)
== pure ($ x) <*> (m, f)
-- ==> af <*> pure x == pure ($ x) <*> af

また同様な流れで、N-Tuple に対しても Applicative を定義可能です。

2-Tuple と Monoid と Applicative

先の導出を別の視点から考えてみます。まず、全ての Monoid は Applicative に落とし込むことが可能です：

import Data.Monoid (Monoid, mempty, (<>))


newtype Pair a b = First a deriving Show

instance Functor (Pair a) where
    fmap _ (First x) = First x

instance Monoid a => Applicative (Pair a) where
    pure _ = First mempty
    First x <*> First y = First (x <> y)

ここで、Phantom Type として Pair を定義しているので、型を部分適用しても種が * -> * となるようになっています。

この実装では型 b (第 2 要素) を完全に無視しているわけですが、もしこれを無視しないのであればどうなるでしょうか？任意の型に対して機能する Applicative のインスタンスとして Identity があるので、これも組み合わせて疑似的に 2-Tuple Applicative を実装してみましょう：

import Data.Monoid (Monoid, mempty, (<>))
import Data.Functor.Identity


newtype Pair a b = First a deriving Show
type Second = Identity
type Tuple a b = (Pair a b, Second b)

instance Functor (Pair a) where
    fmap _ (First x) = First x

instance Monoid a => Applicative (Pair a) where
    pure _ = First mempty
    First x <*> First y = First (x <> y)


pure' :: Monoid a => b -> Tuple a b
pure' b = (First mempty, pure b)

ap' :: Monoid a => Tuple a (b -> c) -> Tuple a b -> Tuple a c
ap' af ax = (fst af <*> fst ax, snd af <*> snd ax)

ここで、型 Tuple a b および pure'，ap' は Applicative のインスタンスとして宣言されたものではないですが、Applicative としての性質を満たし、なおかつ 2-Tuple Applicative と同型です。

Monoidal と Applicative

実は、Applicative と同型な Functor の継承が存在し、これは Monoidal と呼ばれます：

class Functor f => Monoidal f where
    unit :: f ()
    (**) :: f a -> f b -> f (a, b) -- curry (>*<)

-- 自然性
fmap (f *** g) (mx, my) == fmap f mx ** fmap g my

-- 左単位元律
fmap snd (unit ** mx) == mx

-- 右単位元律
fmap fst (mx ** unit) == mx

-- 結合律
fmap (\(a, (b, c)) -> ((a, b), c)) (mx ** (my ** mz)) == (mx ** my) ** mz

Applicative から Monoidal を導出すること，および Monoidal から Applicative を導出することが、相互に可能です。

これより、Monoidal が満たすべき性質から、Applicative にはある種の Monoid 的性質があることもわかります。