最近やったこと - モナドとわたしとコモナド

最近やったことのまとめ。

CPSのモナド変換子

<a href="http://fumieval.hatenablog.com/entry/2013/03/09/180504">モナド変換子の速さを測ってみる - モナドとわたしとコモナド</a>fumieval.hatenablog.com

で作ったmtl-cの塵を払い、Hackageにリリースした。

StateTやWriterTは中でタプルを作ったり壊したりしているが、CPS変換するとそれがなくなり、しかも(>>=)も最適化されるためそれなりのパフォーマンスの向上が期待できる。モナドガチユーザにおすすめだ。

補足 GHC 7.10.1現在、StateTに関しては最適化がうまく効くらしく、Lazy、Strict、CPS版のパフォーマンスはほぼ同じだった。一方、CPS版WriterTは正格にしているためか、Strictの4倍、Lazyの8倍の速度を発揮した。なお、CPS版はベースのモナドが重いときには特に効果的に働く。

後悔なく具現化できるモナド

monad-skeletonというパッケージを公開した。インターフェイスとしては普通のOperationalモナドだが、実装に一工夫がされており、(>>=)が左結合になってもパフォーマンスが落ちにくい特長がある。

基本となる型Skeleton tは、命令tの列がなすモナドである。命令を持ち上げるにはbone :: t a -> Skeleton t a、命令を取り出すときはunbone :: Skeleton t a -> MonadView t (Skeleton t) aを使い、MonadViewに対するパターンマッチによってSkeletonのインタプリタを書ける。

data MonadView t m x where
  Return :: a -> MonadView t m a
  (:>>=) :: t a -> (a -> m b) -> MonadView t m b

命令を集めて君だけのモナドを作ろう！

吹きすさび要素を枯らすイテレータ

witherableの新しいバージョンをリリースした。

Traversableクラスのtraverseは作用を伴った要素のマッピングをするが、このパッケージで定義されているWitherableはtraverseの能力に加え要素の削除も抽象化する。Witherableのメソッドを見ればわかりやすい。

class Traversable t => Witherable t where
    wither :: Applicative f => (a -> f (Maybe b)) -> t a -> f (t b)
    mapMaybe :: (a -> Maybe b) -> t a -> t b
    catMaybes :: t (Maybe a) -> t a
    filterA :: Applicative f => (a -> f Bool) -> t a -> f (t a)
    filter :: (a -> Bool) -> t a -> t a

幅広く使えそうだが、元々は定命のオブジェクト(死ぬオブジェクト)の集まりを管理する関数apprisesの実装のためだけに作った。あえてリストで返さずに継続を使う理由については、モノイドと継続渡しの道具箱も参照されたい。

apprises :: (Witherable t, Monad m, Monoid r)
    => f a -- メッセージ
    -> (a -> r) -- 結果を回収
    -> (b -> r) -- もしくはオブジェクトの亡骸を回収
    -> StateT (t (Mortal f m b)) m r -- 定命のオブジェクトのコンテナへの操作

拡張可能なデータ構造

extensibleを更新した。なんといってもextensibleの売りは、今までの拡張可能系ライブラリとは一線を画し、どんな種でも扱えることだ。

extensibleが提供する拡張可能レコードおよびバリアントは以下の種を持っている。

RecordOf :: (v -> *) -> [Assoc k v] -> *
VariantOf :: (v -> *) -> [Assoc k v] -> *

v -> *のパラメータを利用すれば、*でも* -> *でも* -> * -> *でも、レコードおよびバリアントの対象になる。そのおかげで、単純なレコードだけでなく、多相型も使えるExtensible effects、ファーストクラスパターンマッチ、objectiveと組み合わせればクラスベースオブジェクト指向も実装できるぞ。以下はextensibleとaesonを組み合わせ、要素に型の付けられるJSONパーサを実装する例。

gist.github.com

objective

Michael Snoyman先生のおかげでインスタンスが例外安全になった(https://github.com/fumieval/objective/commit/ffffc5b7afba88155be9c08c1b8204b7cadfe0a4)。もしオブジェクトが例外を投げたとき、例外を発生させる前のオブジェクトにロールバックする。これによって不正な状態の発生を防ぐことができる。オブジェクト指向の実装で、このようにしてオブジェクトの整合性を保つのはなかなか新しいアイデアだと思う。

また、extensibleと組み合わせてExtensible effectsの実現も試みている。山本和彦さん曰くobjective以外でOperationalモナドが本当に役立つ例を見たことがないそうなので、おそらくobjectiveパッケージの一部として提供することになる。

謎のひも

ファイルから音声を読み込むなど、シーク可能なデータを扱いたい場面がある。相対的なものと絶対的なものを合わせればシーク操作はモノイドになるという点に着目し、実験段階だがtapesというものを実装したが、終端の扱いにまだ疑問が残る。開いたり閉じたりする概念は本質的に難しい。