bitterharvest’s diary

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

ゲームの中で信号関数を自在に扱う:アロー記法

1.アロー記法

ここで用いているアロー記法は、John Hughesが定義したものを応用している。もとの理論は次のようになっている。
John Hughesのアロー記法:
1)型のような関数に対する抽象データ型インタフェースである。

2)プロセスのような計算を表現する型に対して特に適している。

3)モナドに関係している。それはアロー記法が計算であることによる。しかし、もっと一般的には、任意のモナド\(m\)はアロー記法を引起すことによる。即ち、Kleisliアロー記法\(\alpha \rightarrow m \beta \)。しかし、逆は真ではない。

4)配線の組合せ子の最小の集合を用意する。

アローとは
1)二引数の型コンストラク

2)三つのオペレータ
 (ア) 持上げ(lifting): arr :: (b -> c) – a b c
 (イ) 合成(composition):(>>>) :: a b c -> a c d -> a b d
 (ウ) 拡張(widening):first :: a b c -> a (b,d) (c,d)

3)代数的法則
 (ア) (f >>> g) >>> h = f >>> (g >>> h)
 (イ) arr (g.f) = arr f >>> arr g
 (ウ) arr id >>> f = f
 (エ) f = f >>> arr id
 (オ) first (arr f) = arr (f x id)
 (カ) first (f >>> g) = first f >>> first g
 (キ) first f >>> arr (id x g) = arr (id x g) >>> first f
 (ク) first f >>> arr fst = arr fst >>> f
 (ケ) first (first f) >>> arr assoc = arr assoc >>> first f

4)関数はアローの簡単な例で次のように対応する。この場合、アローの型コンストラクタは(->)である。
 (ア) arr = id
 (イ) (>>>) = flip (.) (f >>> g = g . fより)
 (ウ) first f = \(b,d) -> (f b, d)

5)ループ組合せ子
 (ア) 全てのアローインスタンスがループを持つとは限らないので、別のクラスのメソッドとなる。
  ① class Arrow -> ArrowLoop a where loop :: a (b, d) (c, d) -> a b c

6)配線組合せ子としては、arr, (>>>), first, loopで十分である。

7)その他に次のものが考えられる。
 (ア) scond :: Arrow a => a b c -> a (b,d) (d, c)
 (イ) (***) :: Arrow a => a b c -> a d e -> a (b, d) (c, e)
 (ウ) (&&&) :: Arrow a => a b c -> a b d -> a b (c, d)

以上の理論を信号関数に応用したのが下図である。
f:id:bitterharvest:20141026194527p:plain

2.アロー記法

アロー記法で信号関数を複雑に合成したシステムがどのように記述できるかを示した。さらに、もう少し簡潔に示せるようにしたのが、アロー記法である。これは、もちろん糖衣構文である。前回の記事で上げたシステムに下図のように信号名をつける。
f:id:bitterharvest:20141026075132p:plain
アロー記法は次のようになっている(ここで、patは信号変数に束縛されるパターンである。それは信号値のexpと照合される。sfexpは信号関数である)。

  proc pat -> do
    pat1 <- sfexp1 -< exp1
    pat2 <- sfexp2 -< exp2
    ......................
    patn <- sfexpn -< expn
    returnA -< exp

上記のシステムはアロー記法を用いると次のようになる。

proc x -> do
  rec
    u <- f -< (x, v)
    y <- g -< u
    v <- h -< (u, x)
  returnA -< y

3.跳ね返ってくるボール

前回の記事で跳ね返ってくるボールのプログラムを作成したが、ここでは、おさらいをする。下図のように質量\(m\)のボールが高さ\(y_0\)から力\(mg\)で落下する。
f:id:bitterharvest:20141026075112p:plain
この時、時間\(t\)での位置\(y\)と速度\(v\)は、質量\(m\)に関係なく、
\begin{eqnarray}
y & = & y_0 + \int v dt \\
v & = & v_0 + \int -9.81 dt
\end{eqnarray}
となる。
また、床に衝突したときは、ボールと床が完全弾性体であれば、その速度は
\begin{eqnarray}
v = -v
\end{eqnarray}
となる。

落下するボールは次のようにプログラムできる。

type Pos = Double
type Vel = Double
fallingBall :: Pos -> Vel -> SF () (Pos, Vel)
fallingBall y0 v0 = proc() -> do
  v <- (v0+) ^<< integral -< -9.81
  y <- (y0+) ^<< integral -< v
  returnA -< (y, v)

4.離散的時間の信号とイベント

Yampaの信号は概念的には連続である。離散的時間の信号は時間の中のある点で定義された信号である。Yampaでは離散的時間の信号を付加的な型を用いることで連続的時間の信号と共通の領域に持ち上げる。付加的な型Eventは、型Maybeに類似しているが、次のようになっている。

data Event a = NoEvent | Event a

離散的時間の信号は次のようになる。

Discrete-time signal = Signal (Event a)

イベント関数の例を以下に挙げる。

tag :: Event a -> b -> Event b
never :: SF a (Event b)
now :: b -> SF a (Event b)
after :: Time -> b -> SF a (Event b)
repeatedly :: Time -> b -> SF a (Event b)
edge :: SF Bool (Event ())
notYet :: SF (Event a) (Event a)
once :: SF (Event a) (Event a)

5.飛び跳ねるボール

イベント関数を用いて、ボールが床に衝突するときを以下のようにHaskellで記述する。

fallingBall’ :: Pos -> Vel -> SF () ((Pos, Vel), Event(Pos, Vel))
fallingBall’ y0 v0 = proc () -> do
  yv@(y,_) <- fallingBall y0 v0 -< ()
  hit <- edge -< y <= 0
  returnA -< (yv, hit `tag` yv)

上記のプログラムで、二つのイベント信号edgeとtagを利用している。edgeはボールが床に衝突したことを知らせるイベントとして、タッグはイベントが起きた状況を知らせるイベントとして用いてる。