Haskell のコンテナ系型クラスとそのインスタンスたち

自分用メモ。
便宜上、以下のクラス定義は GHC の標準ライブラリにあるものとは少し変へて最小化してある。

(ここら辺のクラスはコンテナと一般的に呼ばれてゐるが、何かを容れるものといふよりは物の在り方を示すものといった方が正確な気がするので modifier とでも呼びたい)

Monad 系

Functor

個人的には mappable とでも呼びたい。

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

Functor だが pointed functor でないインスタンス

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

newtype Const a b = Const { getConst :: a }
instance Functor (Const m) where
    fmap _ (Const v) = Const v

Pointed

個人的にはこれを container とでも呼びたい。

注: Pointed は GHC の標準ライブラリには無い。

class Pointed f where
    pure :: a -> f a

Pointed だが pointed functor でないインスタンス

• 集合

Pointed functor

注: Pointed functor は GHC の標準ライブラリには無い。

class (Functor f, Pointed f) => PointedFunctor f where

Pointed functor だが applicative でないインスタンス

そんなものある?

Applicative

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

または以下のように定義しても計算能力は実質的に同等

class PointedFunctor f => Applicative f where
    combine :: f a -> f b -> f (a, b)

Applicative だが monad でないインスタンス

newtype ZipList a = ZipList { getZipList :: [a] }
instance Functor ZipList where
    fmap f (ZipList xs) = ZipList (map f xs)
instance PointedFunctor ZipList where
    pure x = ZipList (repeat x)
instance Applicative ZipList where
    ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

Monad

class Applicative f => Monad f where
    join :: f (f a) -> f a

Monad のインスタンス

• Identity
• Maybe
• []
• Either e
• (->) r
• ST
• IO
• ...

Arrow 系

Category

class Category cat where
    id :: cat a a
    (.) :: cat b c -> cat a b -> cat a c

Category だが pointed category でないインスタンス

data (:~:) a b where
    Refl :: (:~:) a a
instance Category (:~:) where
    id          = Refl
    Refl . Refl = Refl

Pointed category

注: Pointed category は GHC の標準ライブラリには無い。ここでの pointed category は単に pointed functor に倣って名付けたもので、零対象がある圏といふ意味ではない。

class Category cat => PointedCategory cat where
    arr :: (a -> b) -> cat a b

Pointed category だが arrow でないインスタンス

何かあるのかもしれないけど思ひ付かない

Arrow

class PointedCategory a => Arrow a where
    first :: a b c -> a (b, d) (c, d) 

Arrow のインスタンス

instance Category (->) where
    id x = x
    g . f = \x -> g (f x)
instance PointedCategory (->) where
    arr f = f
instance Arrow (->) where
    first f ~(x, y) = (f x, y)

Traversable 系

Foldable

個人的には iterable あるいは collection とでも呼びたい。

class Foldable f where
    foldr :: (a -> b -> b) -> b -> f a -> b

Foldable だが functor/traversable でないインスタンス

• Haskell : An example of a Foldable which is not a Functor (or not Traversable)?

Traversable

個人的には collectable とでも呼びたい。

class (Functor t, Foldable t) => Traversable t where
    sequenceA :: Applicative f => t (f a) -> f (t a)

Traversable のインスタンス

• Identity
• Maybe
• []
• Either e
• (,) a
• ...

Monoid 系

Monoid

class Monoid a where
    mempty  :: a
    mappend :: a -> a -> a

Monoid だが alternative でないインスタンス

これらはホモジーニアスなコンテナではないので alternative はおろか functor ですらない。

instance Monoid b => Monoid (a -> b) where
    mempty _ = mempty
    mappend f g x = f x `mappend` g x

instance Monoid () where
    mempty        = ()
    _ `mappend` _ = ()
    mconcat _     = ()

instance (Monoid a, Monoid b) => Monoid (a,b) where
    mempty = (mempty, mempty)
    (a1,b1) `mappend` (a2,b2) =
        (a1 `mappend` a2, b1 `mappend` b2)

newtype All = All { getAll :: Bool }
instance Monoid All where
    mempty = All True
    All x `mappend` All y = All (x && y)

newtype Any = Any { getAny :: Bool }
instance Monoid Any where
    mempty = Any False
    Any x `mappend` Any y = Any (x || y)

newtype Sum a = Sum { getSum :: a }
instance Num a => Monoid (Sum a) where
    mempty = Sum 0
    Sum x `mappend` Sum y = Sum (x + y)

newtype Product a = Product { getProduct :: a }
instance Num a => Monoid (Product a) where
    mempty = Product 1
    Product x `mappend` Product y = Product (x * y)

注: GHC の標準ライブラリには Monoid (Maybe a) のインスタンスも含まれるが、 Alternative Maybe や MonadPlus Maybe とは異なる働きをする。

instance Monoid a => Monoid (Maybe a) where
  mempty = Nothing
  Nothing `mappend` m = m
  m `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Alternative

Monoid な applicative

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a

Alternative だが monad plus でないインスタンス

Monad plus のインスタンスが満たすべき公理について複数の流儀があり、それによって Maybe を monad plus と見做してよいかどうかが変はる。

Monad plus

Monoid な monad

class Monad m => MonadPlus m where
   mzero :: m a 
   mplus :: m a -> m a -> m a

Monad plus のインスタンス

instance MonadPlus [] where
   mzero = []
   mplus = (++)

instance MonadPlus Maybe where
   mzero = Nothing
   Nothing `mplus` y = y
   x       `mplus` _ = x

Arrow plus

Monoid な arrow

class Arrow a => ArrowZero a where
    zeroArrow :: a b c

class ArrowZero a => ArrowPlus a where
    (<+>) :: a b c -> a b c -> a b c

Arrow plus のインスタンス

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }
instance Monad m => Category (Kleisli m) where
    id = Kleisli return
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f)
instance Monad m => PointedCategory (Kleisli m) where
    arr f = Kleisli (return . f)
instance Monad m => Arrow (Kleisli m) where
    first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d))
instance MonadPlus m => ArrowZero (Kleisli m) where
    zeroArrow = Kleisli (\_ -> mzero)
instance MonadPlus m => ArrowPlus (Kleisli m) where
    Kleisli f <+> Kleisli g = Kleisli (\x -> f x `mplus` g x)