【Haskell】2-Tuple の Functor としての性質，Applicative としての性質

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的性質があることもわかります。