読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

Netwireでゲームを作成する(5)

8.各圏へのインスタンス

前回の記事で、振舞いを次のように定義した。

newtype Behavior t a b = Behavior { stepBehavior :: t -> a -> (b,Behavior t a b) }

この段階では、型として定義しただけなので、いろいろな性質を持たせるために、必要な型クラスのインスタンスにする。以下で、インスタンス化を行うが、そこでは、いくつかのモジュールを必要とする。それを示したのが下記である。

{-# LANGUAGE TemplateHaskell #-}

import Control.Lens
import Control.Arrow
import Control.Category
import Prelude hiding ( (.), id )
import Control.Applicative
import Data.Semigroup

8.1 Arrowのインスタンス

Arrowはスイッチを表現するために、なくてはならない型クラスである。過去の記事で、Yampaの信号関数を説明するときにArrow記法に触れた。Arrow記法を用いることで、逐次処理、分岐(スイッチ)、繰り返しが可能になる。


型クラスArrowは次のようにCategoryのサブクラスとして定義されている。Arrowはメソッドとしてarrとfirstを有する。

class Category a => Arrow a wherewhere
  arr :: (b -> c) -> a b c
  first :: a b c -> a (b,d) (c,d)

Haskellのよいところは、あるいは、圏論のよいところは、抽象度の高い定義に対して多様な解釈を許すことである。型クラスArrowもとても抽象度が高いので様々な見方から説明できる。例えば、Yampaでの信号関数のように、あるいは、Haskell/Understanding arrowsの記事にみられるように、Arrowを工場に見立て、写像を機械とみなし、機械をコンベアの上に載せることで実現できる逐次処理、並行処理、並列処理などを例示して説明できる。このように、顧客にあわせて説明できるので、抽象度の高い定義はとても便利である。このことが、ドメイン固有言語を容易に作成できる能力をHaskellに与えている。

arrの定義は、カリー化したときの互換図を思い出してほしい。
f:id:bitterharvest:20150616091730p:plain
上記の図で、\(f: A \times B \rightarrow C\)をカリー化すると\(g: A \rightarrow C^B\)となる。arrの定義は、指数対象\(C^B\)が与えられた時、カリー化関数で対象Aから\(C^B\)への写像を与えていると考えればよい。

firstの定義は次のように説明できる。まず、上記の互換図から次の互換図を得る。
f:id:bitterharvest:20150616093940p:plain
firstは上記の互換図のカッコの部分、すなわち左側(first)の部分を表したものである。右側の\( \times D \)はごみのようなものだ。

しかし、この互換図を下記のように書き換えることが可能である。
f:id:bitterharvest:20150616094235p:plain
シグネチャでの右側の項はこれを表したものである。

この型クラスには次の制約がある。なお、下記で(>>>)は関数合成である。通常は、(.)を用いるが、ここではArrowの通例に従った。

arr id = id
arr (f >>> g) = arr f >>> arr g
first (arr f) = arr (first f)
first (f >>> g) = first f >>> first g
first f >>> arr fst = arr fst >>> f                     -- fstは対のペアの最初の要素
first f >>> arr (id *** g) = arr (id *** g) >>> first f -- ***は後で説明
first (first f) >>> arr assoc = arr assoc >>> first f where assoc ((a,b),c) = (a,(b,c))

上記で、arr f >>> arr gの部分で用いられている(>>>)の型シグネチャは、

(>>>) :: a b c -> a c d -> a b d

である。
arr,first,(>>>)を図で表すと以下のようになる。
f:id:bitterharvest:20150616102551p:plain

arrowで用意した関数arr, firstを利用して次の有用な関数を作成できる。

(***) :: a b c -> a d e -> a (b, d) (c, e)
(&&&) :: a b c -> a b d -> a b (c, e)

f:id:bitterharvest:20150616104047p:plain

そこで、型Behaviorを以下のようにして型クラスArrowのインスタンスにする。

fix f = f (fix f)

instance Arrow (Behavior t) where
  arr f = fix $ \r -> Behavior $ \t a -> (f a,r)
  first f = Behavior $ \t (b,d) ->
    let (c,fn) = stepBehavior f t b
    in ((c,d),first fn)

8.2 Categoryのインスタンス

BehaviorをArrowのインスタンスにしたので、そのスーパークラスであるCategoryのインスタンスにもしておく必要がある。

Categoryは、圏論での圏である。圏は、①対象の集まりを有する②射の集まりを有する③射はソースからターゲットへと写像する④恒等射が存在する⑤関数の合成が存在するであった。また、満たさなければならない条件は、①恒等射に対しては単位律が成り立つ。即ち、いかなる射に恒等射を(右からでも左からでも)施しても、元の射になる。②関数を合成したとき、結合律が成り立つ。即ち、どの部分から関数の合成を計算しても変わらないである。

Categoryの定義は次のようになっていて、メソッドとして恒等射idと合成(.)を有する。

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

そこで、Behaviorを次のようにして、Categoryのインスタンスとする。

instance Category (Behavior t) where
  id = arr id
  x . y = Behavior $ \t a ->
    let (yr, yn) = stepBehavior y t a
        (xr, xn) = stepBehavior x t yr
    in (xr, xn . yn)

上記で、x.yは、aという入力を受けて、yがyrという出力を出し、xはyrという入力を受けて、xrという出力を出す。また、この時、yの新しい振舞いはynになり、xの新しい振舞いはxnになる。

8.3 Semigroupのインスタンス

集合\(S\)と二項演算が与えられ、そこで、結合律が成り立つとき半群という。1以上での自然数での加算は半群の例である。自然数の加算では0が恒等射であるが、半群は恒等射があることを要求していない。

Categoryの定義は次のようになっていて、メソッドとして二項演算子<>を有する。

class Semigroup a where
  (<>) :: a -> a -> a

振舞いについても、出力と振舞いの型が同じである時、二つの振舞いを一つの振舞いにまとめられるように、次のようにインスタンス化する。

instance (Semigroup b) => Semigroup (Behavior t a b) where
  x <> y = Behavior $ \t a ->
    let (xr,xn) = stepBehavior x t a
        (yr,yn) = stepBehavior y t a
    in (xr <> yr,xn <> yn)

8.4 Functorのインスタンス

キーボードからのイベントを処理するときに、Functorを用いた。そこで、Behaviorをこのインスタンスとする。Functorについては馴染んでいる人も多いと思うが、その定義は次のようになっている。また、メソッドとしてfmapを有する。

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

なお、次の規則を満たさなけらばならない。

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

Behaviorは、次によりFunctorのインスタンスにする。

instance Functor (Behavior t a) where
  fmap f b = Behavior $ \t a ->
    let (br,bn) = stepBehavior b t a
    in (f br,fmap f bn)

8.5 ApplicativeとProfunctorのインスタンス

使い勝手を良くするために、ApplicativeとProfunctorのインスタンスにもする。これは次のように行う。
なお、ApplicativeとProfunctorについては、別の記事で説明する予定である。

Applicativeの定義は次のようになっている。pureという関数は後続の記事でキーボードの入力を速度に変換するときに使用する。

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

インスタンス化は次のように行う。

instance Applicative (Behavior t a) where
  pure = arr . const
  f <*> x = Behavior $ \t a ->
    let (fr,fn) = stepBehavior f t a
        (xr,xn) = stepBehavior x t a
    in (fr xr,fn <*> xn)

Profunctorの定義は次のようになっている。

class Profunctor h where
  dimap :: (c -> a) -> (b -> d) -> f a b -> f c d

インスタンス化は次のように行う。

instance Profunctor (Behavior t) where
  dimap l r x = Behavior $ \t a ->
    let (xr,xn) = stepBehavior x t (l a)
    in (r xr,dimap l r xn)