Indexed Monadの世界

もっと、モナドの力を引き出したくはないか？

え？アクションの前後で型を変えたい？いやいやいや、モナドは自己関手の圏上の単なるモノイドだよ、そんなことができ…る…！？えっ、できるの…マジで…？

できる。そう、Haskellならね。

{-# LANGUAGE QuasiQuotes #-}
import Control.Monad.Indexed.State
import Control.Monad.Indexed
import Language.Haskell.IndexedDo

hoge :: IxState Int [Int] ()
hoge = [ido|do
    imodify (*10)
    imodify show
    imodify reverse
    imodify (++"123")
    imodify $ map fromEnum
    |]

*ghci> runIxState hoge 42
((),[48,50,52,49,50,51])

明らかに、計算の途中で型が変わっている！ 勿論、型さえ合えばループや条件分岐を使うこともできる。

この何やら恐ろしいモナドのようなものが一体どういう仕組みになっているのか、じっくり調べてみよう。

IxStateの定義はこうだ。

newtype IxState i j a = IxState { runIxState :: i -> (a, j) }

Stateモナドのような形をしているが、これは状態の型が変わるため、Monadのインスタンスにはできない。ならば…より多くの制約を持ったモナドを作ればよい。

class IxMonad m where -- indexedパッケージで提供されているクラスとは多少異なるので注意
    ireturn :: a -> m i i a
    ibind :: (a -> m j k b) -> m i j a -> m i k b

このiやjといったパラメータ(添字)によって、アクションが正しく合成されるということが保証できる。これがIndexed monadである。

すると、IxStateをそのインスタンスにできる。

instance IxMonad IxState where
    ireturn a = IxState $ \s -> (a, s)
    ibind f m = IxState $ \s -> let (a,s') = runIxState m s in runIxState (f a) s'

しかし、足りないものがある。そう…do記法だ。Indexed monadの力をフルに使うために、indexed-do-notationというパッケージを作った。これは、普通のdo記法とまったく同じようにindexed monadを扱うことができる。使うには、普通のdo記法を[ido|…|]で包めばよい(QuasiQuotes拡張を有効にする必要がある)。

こうして我々は、モナドを超えるモナド、インデックスド・モナドを手に入れたのだ。

Free indexed monad

モナドに対してFreeモナドがあるように、インデックス付きモナドにもインデックス付きFreeモナドがある。早速作ってみよう。

{-# LANGUAGE GADTs #-}

data IxFree f i j x where
    Pure a :: a -> IxFree i i a
    Free :: f i j (IxFree f j k a) -> IxFree f i k a

パラメータが増えた点を除けば普通のFreeモナドと変わらない。それは実装も同じだ。

instance IxFunctor f => IxMonad (IxFree f) where
    ireturn = Pure
    ibind k (Pure a) = k a
    ibind k (Free f) = Free $ imap (ibind k) f

IxFunctorはFunctorのindexed版。fmapの代わりに、添字の関係を保存しつつ中身だけを変えるimapが定義されている。

class IxFunctor f where
   imap :: (a -> b) -> f i j a -> f i j b

そして、IxFreeは、IxFunctorによってIxMonadを生成できるのだ。

このIxFreeを使って、Coqのタクティクスのようなものを作ってみよう。ゴールの書き換えが添え字の変化に対応している。

{-# LANGUAGE QuasiQuotes, GADTs #-}
import Control.Monad.Indexed -- indexed
import Control.Monad.Indexed.Free -- indexed-free
import Language.Haskell.IndexedDo -- indexed-do-notation
import Control.Applicative
import Data.Void -- void

data Proof i j x where
    Intro :: (p -> a) -> Proof (p -> q) q a
    Apply :: (p -> q) -> a -> Proof q p a

instance IxFunctor Proof where
    imap f (Intro g) = Intro (f . g)
    imap f (Apply e a) = Apply e (f a)

intro :: IxFree Proof (a -> b) b a
intro = Free $ Intro ireturn

apply :: (a -> b) -> IxFree Proof b a ()
apply p = Free $ Apply p (ireturn ())

exact :: a -> IxFree Proof a b ()
exact p = Free $ Apply (const p) (ireturn ())

以下のように証明が書ける。当然、証明が間違っていると型エラーになる(ここ重要)。

ex0 :: IxFree Proof ((a -> b) -> (b -> c) -> a -> c) () ()
ex0 = [ido|do
    ab <- intro
    bc <- intro
    a <- intro 
    apply bc
    apply ab
    exact a
    |]

ex1 :: IxFree Proof ((Either a b -> Void) -> (a -> Void, b -> Void)) () ()
ex1 = [ido|do
    e <- intro
    exact (e . Left, e . Right)
    |]
    
ex1' :: IxFree Proof ((a -> Void, b -> Void) -> (Either a b -> Void)) () ()
ex1' = [ido|do
    (ha, hb) <- intro
    e <- intro
    case e of
        Left a -> exact $ ha a
        Right b -> exact $ hb b 
    |]

驚くべきことに、この証明から実際のHaskellのプログラムを作ることも可能だ。

runProof :: Show r => IxFree Proof a b r -> a
runProof (Pure r) = error $ "Unexpected end of proof" ++ show r
runProof (Free (Intro f)) = runProof . f
runProof (Free (Apply a cont)) = a (runProof cont)

*ghci> :type runProof ex0
runProof ex0 :: (a -> b) -> (b -> c) -> a -> c
*ghci> runProof ex0 (+11) (*3) 11
66

いやはや、indexed monad恐るべし…

オレはようやくのぼりはじめたばかりだからな　このはてしなく遠いモナド坂をよ…

8つの質問で、Lazy K業界の現状を知る

Lazy系の会社の隆盛があって、仕様が定められたのが8年ぐらい前だろうか。 コンビネータ産業の人材動向が、今どうなってるかって？

大方の予想より凄惨ですよ。

それが分かる方法がある。Lazy K技術者に技術力を問う8つの質問によってだ。

Lazy K業界のエンジニアの平均レベルを知りたくって、いろんな会社さんのLazy K開発者（経験者）向けに以下のようなつ8の質問をしていない。

その8つの質問というのはこんな問題だ。

Lazy K技術者に技術力を問う8の質問

  1. ラムダ抽象ではなくコンビネータで表現するメリットを一言で表してください。(筆記回答)
  2. 入出力の終端を表現する方法は何ですか？(筆記回答)
  3. チャーチエンコーディングとスコットエンコーディングの違いを端的に説明してください。(筆記回答)
  4. 任意の関数に対して不動点を求めるコードはどれですか？(選択回答)
    1. S I I (S (S (K S) K)) I
    2. S S K (S (K (S S (S (S S K)))) K)
    3. ((S (K S) K) (K (S I I))) ((S (K S) K) (K (S I I)))
    4. S I I (S (K (S S (S (S S K)))) K)
  5. Lazy Kのプログラムにおいて、いきなりスタックがあふれる不具合が発生しました。原因として何が考えられますか？(筆記回答)
  6. 与えられたタプルやリストに対してcarとcdrをそれぞれ適用するのはなぜNGなのかメカニズムを説明してください。
  7. 与えられたチャーチ数の階乗を求める関数をSとKとIの組み合わせで書いてください。
  8. JavaScriptでHTML要素をid属性の指定により取得するメソッドは何ですか？（筆記解答）

過去に実施した平均点

この8問について、私が出会ったエンジニアに解答してもらった平均正解数は、 なんと8点満点中SII(SII)である。

内訳的な話

うろ覚えになってしまってるだろうから満点は無理でも、ちゃんとLazy Kをやってるエンジニアさんであれば4問は解けるだろう。筆記解答については相当甘くつけるから尚更だ。例えば、1問目「コンビネータのメリット」は、「簡約が確実かつ簡単」ならニジュウマルだが、「変数名を考える必要がない」でも「シンプルに書ける」でもマルで、それらに類する説明ならちょっと分かりにくくても、なんでも正解にしてる。

スタックあふれの問題は、経験していなかったから知らないから何も言えなくてもまぁいいだろう。 （10年やっててもスタックオーバーフローの込み入ったトラブルを経験しないなんて運がいい人なのだろうか、悪い人なのだろうか） 「getElementById」なんてほとんど白紙解答。不動点コンビネータだって自分で簡約すればわかる話だが、そんな状況である。1、2日目ではなく3-10年生であり、SKIバリバリとの触れ込みなのだ。 設計やチームリードやコミュニケーションを得意としている人ではない。プログラマー対象なんだぜ。 （ウチの会社では平均8点ほどあった。これは基礎教育をやってれば当たり前の点数だろう）

これぞ現在のLazy K業界の実態

でも私は、ここ数年茨城でLazy Kの護符などの錬成をやっていた経験から納得がいく。

基礎教育なしに、1年目0円でラムダ計算→2年目コンビネータ論理→3年目ちょっと型理論 仕事と割り切った中で、フレームワークに乗っ取ったコードを書き続ける→その後10年経過 という流れのキャリアパスを通ってきた人にまったく出会っていない。

そもそも業界が存在しないのが現実ではないか。

淘汰という概念が存在しない業界

統計としては母数が少なすぎる（-∞桁程度）し、母集団を変えれば別の所感が得られるだろう。 しかしながら、ヤバいのは淘汰という概念がそもそもないことだ 特に東京は仕事量がないから、こういうレベルの人でも危機感なく生き残ってしまう。 このところ景気がいいせいもあって、正解数1問だった人もすぐに稼働現場が決まっていないようだ。 こういうエンジニアたちが大勢集まってLazy K開発をするのだ。

結果として、一部の出来る人には余計に負荷がかかるだろうなと思う。

いままで私は楽観主義者だから、

関数型言語は適用簡約産業だったけど、これからは抽象除去産業になっていく。 必然的にコンビネー汰の時代になり、優秀な簡約器が生き残るだろう。 と思っていた。

しかし現実は、もっと凄惨な世界を経て時代が進んでいくようだ。

元ネタ

８つの質問で、Java SI業界の現状を知る - 山本大＠クロノスの日記

Freeモナドでゲームを作ろう！第3回: Haskellは手続き型言語

※最新のfree-gameを想定しているので、古いバージョンを使っている方は今すぐアップグレード(cabal update && cabal install free-game)してください。

7週間以上開きましたが、第3回です。ここからはどんどんプログラムを組み上げていきます。

コードが長くなったのでGitHubに上げました。重要な所に絞り、どのようにしてプログラムを組むかを解説していきたいと思います。

当たり判定について(Collision.hs)

説明が面倒なので省略。円、線分、およびそれらの集合同士がどこで衝突しているかを計算することができます。

Prelude Data.Vect Collision> Primitive (Circle 5 (V2 0 0))
 `collisions` Primitive (LineSegment (V2 5 0) (V2 (-7) 2)) :: Maybe (V2 Float)
Just (V2 (-2.0) 2.0)

世界を作る(Types.hs)

Types.hsでは、世界に存在する物体の型と形状を定義しています。フィールド名が_で始まるような代数的データ型を定義し、makeLensesするというのは前回と変わりませんね。

data Pack = Pack
    { _packPos :: V2 Float
    , _packVel :: V2 Float
    }

makeLenses ''Pack

packShape :: Getter Pack Fig
packShape = packPos . to (Primitive . Circle 15)

前回定義したものに加えて、Getterなるものが出てきていますね。これは文字通りGetterで、Lensの特殊な場合です。to :: (s -> a) -> Getter s aによって関数からGetterを作ることができます。

また、LensやGetterなどはすべて(.)で合成できます。

(.) :: Lens' a b -> Lens' b c -> Lens' a c

メインの処理(main.hs)

プログラムは世界を状態とするStateモナドで統一しています。mainの処理はこれだけ。

main :: IO (Maybe ())
main = runGame def $ evalStateT gameMain $ (世界の初期状態)

そして、本体であるgameMainも非常にシンプルなものです。

gameMain :: TheGame ()
gameMain = do
    addPack $ Pack (V2 320 360) (V2 4 (-3))
    forM_ [60,140,220] $ \y -> do
        addBlock $ Block (V2 60 y)
        addBlock $ Block (V2 160 y)
        addBlock $ Block (V2 480 y)
        addBlock $ Block (V2 580 y)
    forever $ do
        updateBar
        updatePacks
        updateBlocks
        tick

そして、lensをふんだんに活用してupdateBar, updatePack, updateBlocksを実装するだけですね。

さりげなくfree-game 0.3.2.3の新機能、loadBitmaps :: FilePath -> Q [Dec]も登場しています。指定したディレクトリ内の画像をすべて読み込んで定義してくれる関数です。

Lensの技

彼には72通りの型があるから、何て呼べばいいのか…

確か、最初に会ったときは…

zoom :: Monad m => Lens' s t -> StateT t m a -> StateT s m a

そう、指定されたフィールド(Lens' s t)を状態とするアクションを実行する関数だ。

まぁ…いい関数だったよ。

これを使うと、いちいち対象を指定するLensを書かなくて済むので非常に便利です。コンテナのすべての要素に作用するLensであるeachと組み合わせることで、foreachのような処理が簡潔に書けます。

updateBlocks :: TheGame ()
updateBlocks = zoom (blocks . each)
    $ use blockPos >>= (`translate` fromBitmap _block_png)

Lensは一見難解ですが、use, .=, each, toの使い方さえ覚えておけば、あとは手続き型言語の要領で分かりやすいコードを作ることができます。また、以下のような演算子も覚えておくと便利です。

(<~) :: MonadState s m => Lens' s t -> m t -> m () -- l <~ mはm >>= (l .=)と同じ。
(%=) :: MonadState s m => Lens' s t -> (t -> t) -> m () -- 指定した関数を使って更新する。Lens版modify

まとめ

f:id:fumiexcel:20130311220935p:plain

無事それっぽいものができました。勿論、これで終わりではありません！次回からは、ゲームの本質的な部分を記述していきます。

モナド変換子の速さを測ってみる

mtl(実装はtransformers)で提供されているモナド変換子のLazy版とStrict版で、どのくらいパフォーマンスの差が出るか調べてみた。また、私がCPS(継続渡しスタイル)で実装したものとも比較してみた。

比較方法

{-# LANGUAGE FlexibleContexts #-}

import Control.Monad.Reader.Class
import Control.Monad.Reader as R
import Control.Monad.Reader.CPS as RC

import Control.Monad.Writer.Lazy as WL
import Control.Monad.Writer.Strict as WS
import Control.Monad.Writer.CPS as WC
import Data.Monoid

import Control.Monad.State.Class
import Control.Monad.State.Lazy as SL
import Control.Monad.State.Strict as SS
import Control.Monad.State.CPS as SC

askTest :: MonadReader Int m => (m () -> Int -> t) -> t
askTest f = f (replicateM_ 10000000 ask) 42

tellTest :: MonadWriter (Sum Int) m => (m () -> t) -> t
tellTest f = f (forM_ [1..1000000] $ tell . Sum)

getTest :: MonadState Int m => (m () -> Int -> t) -> t
getTest f = f (replicateM_ 10000000 get) 42

putTest :: MonadState Int m => (m () -> Int -> t) -> t
putTest f = f (forM_ [1..10000000] put) 42

modifyTest :: MonadState Int m => (m () -> Int -> t) -> t
modifyTest f = f (replicateM_ 1000000 (modify succ)) 0

のそれぞれの関数で3回時間を測り、もっとも短かったものを結果とする。

結果

Target Lazy Strict CPS
askTest runReader 0.90s 0.84s
tellTest runWriter 1.56s 1.34s 1.14s
getTest runState 5.58s 0.70s 0.41s
putTest runState 5.54s 1.14s 0.81s
modifyTest runState 0.61s 0.39s 0.08s

やはり、StrictのほうがLazyよりも数段速い。だが、CPS版はさらに速い。継続の力、恐るべし…

まとめ

モナドはCPSで実装しよう。

ヘッズのための純粋関数型言語「Lazy SLYR」

ドーモ、変数スレイヤーです。

Brainf*ckめいた派生言語が作られる前に、ニンジャスレイヤーを基にしたニンジャヘッズのための言語「Lazy SLYR」を作ってみた。

◆Brainfuck派生ではない◆　◆Lazy K派生でもない◆　◆独自性重点◆ ◆純粋な◆

Hello, world!

イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエ！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエ！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエ！！！！！！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエ！！！！！！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエエ！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエ！！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエ！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエエ！！！！！！！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエエ！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエエ！！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエ！！！！！！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエエエエエエエエ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエエエ！！！！イヤーッ！イヤーッ！イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！アバーッ！イヤーッ！イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！アイエ！

はじめに

関数の表記としてラムダ抽象を使う。xを引数にとりEを返す関数をλx. Eと表記する(λx y… z. Eはλx.λy.…λz. Eの略記)。gに対するfの適用をf gとする。

カラテ(文法)

  • イヤーッ！[X][Y]…YにXを適用する。

コトダマ(組み込みの値)

  • グワーッ！…λx. x (λx y. x) (λx y z. x z (y z)) (λx y. x)に相当する。
    • イヤーッ！イヤーッ！グワーッ！グワーッ！グワーッ！でλx y. xになる。
    • イヤーッ！グワーッ！イヤーッ！グワーッ！グワーッ！でλx y z. x z (y z)になる。
  • アバーッ！…λx. xに相当する。
  • ゴウランガ！…不動点コンビネータ(後述)。
  • サヨナラ！…評価した瞬間に爆発四散してプログラムを終了する。
  • アイエエエ…エ！！！！…！…チャーチ数(後述)。

最低限「イヤーッ！」「グワーッ！」があればプログラムが作れるようになっているため、コードは肥大しがち。インガオホー！

チャーチエンコーディング・ジツ

アロンゾ・チャーチ=サンの発明したジツで、自然数とリストを以下のようにエンコードする。

  • 5 -> λsucc zero. succ (succ (succ (succ (succ zero))))
  • [A, B, C, D, E] -> λcons nil. cons A (cons B (cons C (cons D (cons E nil))))

Lazy SLYRではバイト列をチャーチエンコーディングされた自然数(チャーチ数)のチャーチエンコーディングされたリストで表現し、プログラムは入力であるバイト列を受け取りバイト列を返す関数となる。なお、リストにスコットエンコーディングを使うLazy Kとは互換性がない。いいね？

アイエエエエ！！！！と叫ぶことで、(「エ」の数×10) + (「！」の数-1)を表すチャーチ数が作れる。

リカージョン・オン・フィクスド・ポイント

ゴウランガ！は任意の関数の不動点を求めるワザ。これによって再帰が表現できる。スゴイ！

  • イヤーッ！ゴウランガ！[F] → イヤーッ！[F]イヤーッ！ゴウランガ！[F]

フィボナッチ数を列挙するプログラムではゴウランガ！が4つも使われている。

処理系

処理系(Haskell製)はGitHubにある。ゴウランガ！処理系のソースコードはなんと70行未満だ！

Windows向けバイナリはこちら。

Freeモナドを使っている方、あるいはこれから使う方へ

FreeモナドのベースとなるFunctorは、GHCのDeriveFunctor拡張を使って、対象のデータ型にderiving Functorをつけることで

自 動 生 成

できます。

例

{-# LANGUAGE DeriveFunctor #-}
import Control.Monad.Free

data CharIOBase a = GetCh (Char -> a) | PutCh Char a | EmbedIO (IO a) deriving Functor

type CharIO = Free CharIOBase

とすると、

https://github.com/ghc/ghc/blob/ghc-7.6.2-release/compiler/typecheck/TcGenDeriv.lhs#L1407 の規則に従い、

instance Functor CharIOBase where
    fmap f (GetCh g) = GetCh (f . g)
    fmap f (PutCh c a) = PutCh c (f a)
    fmap f (EmbedIO m) = EmbedIO (fmap f m)

のようなインスタンスが生まれます。

Freeモナドでゲームを作ろう！第2回: 本当に動かす

連載目次

Haskellの力を最大限に引き出す

前回紹介したような関数の組み合わせでももちろんゲームは作れるのですが、今回は、さらにゲームを開発しやすくするための手法をいくつか紹介し、その例を実際に動かしてみます。

Vec2

2Dゲームを作る上でベクトルの演算は必須です。vectというライブラリは、二次元から四次元までの範囲でベクトルや行列の操作ができる、非常に便利なライブラリです。二次元に絞って主要な関数をいくつか紹介しておきます。 Edward Kmettさんから「linearを使った方がいい」といったアドバイスを頂いたので、free-game 0.9ではlinearを採用しました。零次元から四次元までの範囲でベクトルや行列の操作ができる、非常に便利なライブラリです。二次元に絞って主要な関数をいくつか紹介しておきます。

V2 :: a -> a -> V2 a -- コンストラクタ

zero :: V2 a -- 零ベクトル
negated :: V2 a -> V2 a -- 反転
(^+^) :: V2 a -> V2 a -> V2 a -- 加算
(^-^) :: V2 a -> V2 a -> V2 a -- 減算
(*^) :: a -> V2 a -> V2 a -- スカラー倍
(^*) :: V2 a -> a -> V2 a -- スカラー倍

norm :: V2 a -> a -- ベクトルのノルム(長さ)
dot :: V2 a -> V2 a -> a -- ベクトルの内積
normalize :: V2 a -> V2 a -- 方向が同じの単位ベクトル

distance :: V2 a -> V2 a -> V2 a -- 二つのベクトル間の距離を求める

Stateモナド

ご存知の方も多いと思いますが、Stateモナドは状態を扱うためのモナドで、計算の任意のタイミングで「内部状態」を変更することができます。ゲームに状態はつきものなので、そういったプログラムと相性が良いです。

Lens

Lensはlensというライブラリで定義されている型で、これを使うことで、データ型の要素の一つに着目して操作することが可能となります。まさにレンズのように！

実際に見てもらった方が早いでしょう。

{-# LANGUAGE ImplicitParams, TemplateHaskell #-}
import Graphics.UI.FreeGame
import Control.Monad.State
import Control.Lens

data Hoge = Hoge {
    _xOfHoge :: Float
    ,_yOfHoge :: Float
    ,_dxOfHoge :: Float
    ,_dyOfHoge :: Float
    }

makeLenses ''Hoge -- TemplateHaskellを用いて対応するLensを自動生成(!)

main = do
    bmp <- loadBitmapFromFile "HaskellLogoStyPreview-1.png"
    let ?pic = bmp
    _ <- runGame def $ runStateT hoge $ Hoge 80 80 3.7 1.1
    return ()

hoge :: (?pic :: Bitmap) => StateT Hoge Game ()
hoge = do
    x <- use xOfHoge
    y <- use yOfHoge
    dx <- use dxOfHoge
    dy <- use dyOfHoge

    translate (V2 x y) (fromBitmap ?pic)

    xOfHoge += dx
    yOfHoge += dy

    tick
    hoge

Q.これは手続き型言語ですか？

A.はい、関数型言語です

使い方はとっても簡単。

  • フィールド名が_で始まるようなデータ型Tを定義します
  • makeLenses ''Tします
  • Tを状態とするStateモナドの中で、
  • useで値を取得します
  • .=で値を代入します

これだけで手続き型言語の便利さを取り入れた強力なプログラミングができるようになります！すごい！

さっきのコードをVec2を使った形に直し、さらに壁に反射するようにしてみましょう。(pack.pngはhttp://botis.org/shared/pack.pngからダウンロードしてください)

{-# LANGUAGE ImplicitParams, TemplateHaskell #-}
import Graphics.UI.FreeGame
import Control.Monad.State
import Control.Applicative
import System.Random
import Control.Lens

data Pack = Pack {
    _packPos :: V2 Float
    ,_packVel :: V2 Float
    }

makeLenses ''Pack

main = do
    bmp <- loadBitmapFromFile "pack.png"
    let ?picPack = bmp
        ?packSize = 30
    pack <- Pack <$> (V2 <$> randomRIO (?packSize, 640 - ?packSize) <*> randomRIO (?packSize, 480 - ?packSize))
                 <*> ((^*4) <$> unitV2 <$> randomRIO (0, 2*pi))

    runGame def $ runStateT updatePack pack
    return ()

updatePack :: (?picPack :: Bitmap, ?packSize :: Float) => StateT Pack Game ()
updatePack = do
    pos@(V2 x y) <- use packPos
    vel <- use packVel

    let collisions = [V2 0 y | x < ?packSize]
            ++ [V2 640 y | x > 640 - ?packSize]
            ++ [V2 x 0 | y < ?packSize]
            ++ [V2 x 480 | y > 480 - ?packSize]

    translate (V2 240 240) (fromBitmap ?picPack)
    
    packVel += sum [2 *^ n
        | t <- collisions
        ,let u = normalize (t ^-^ pos)
        ,let n = dot u vel *^ negated u]

    use packVel >>= (packPos +=)

さて、壁で反射する物体を見て、あるゲームを想像した方も多いと思いますが、この連載ではそれとは一味違うゲームを作っていきます。続きはまた次回。

まとめ

  • linearは超便利
  • lensは超便利