快速のExtensible effects

extensibleは拡張可能レコードだけでなく拡張可能作用(extensible effects)も用意している。拡張可能作用は一時期Haskell界隈で話題になったものの、今では人気も下火になってしまった。新しいバージョンをリリースした今、拡張可能作用の動機と使い方について改めて紹介しよう。

難行の一次関数

Haskellモナドをカスタマイズする方法としては、transformersモナド変換子がよく使われている。モナド変換子は、モナドをパラメータとして取り、新たな能力を付与したモナドにする構造だ。例えば、StateT sはモナド変換子の一つである。任意のアクションm aliftを使ってStateT s m aに変換できる。

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

他にもReaderT, WriterT, MaybeTなどの変換子があり、好きなように組み合わせてモナドを作れる。しかし、変換子を積んだ分だけliftを適用しなければいけないので、そのまま使うのは非常に不便だ。

苦行の二次関数

mtlというライブラリは、モナドの固有アクションを抽象化する型クラスを定義している。 MonadStateはその一つで、関数従属性m -> sは、mの型が決まればsもわかるという制約を示している。もちろんStateTはそのインスタンスになる。

class Monad m => MonadState s m | m -> s where
  get :: m s
  put :: s -> m ()
  state :: (s -> (a, s)) -> m a

instance Monad m => MonadState s (StateT s m)

ベースのモナドがMonadStateならば、単体ではStateの能力を持たないモナドについてもインスタンスが定義できる。そのため、書き手側がliftを書く必要がなく、使いやすい。

MonadState s m => MonadState s (MaybeT m)
MonadState s m => MonadState s (ListT m)
(Monoid w, MonadState s m) => MonadState s (WriterT w m)
(Monoid w, MonadState s m) => MonadState s (WriterT w m)
MonadState s m => MonadState s (IdentityT m)
MonadState s m => MonadState s (ExceptT e m)
(Error e, MonadState s m) => MonadState s (ErrorT e m)
MonadState s m => MonadState s (ReaderT * r m)
MonadState s m => MonadState s (ContT * r m)

しかし、モナドを作る側にとっては厄介な代物だ。新しい変換子を作るたび、mtlにある分だけでMonadCont, MonadError, MonadReader, MonadState, MonadWriter, MonadIOの6つのインスタンスを定義しないといけない。しかもMonadContMonadWriterは単なるliftでは書けずかなり厄介だ。

クラスを作る場合、今度は自前のモナドに加え、AccumT, ContT, ExceptT, IdentityT, MaybeT, RWST 二種、ReaderT, WriterT二種、StateT二種の計12個のインスタンスも作らされる。変換子と対応するクラスを作るたびに加速度的に労力が増し、いつかは破綻する。

拡張可能作用

Extensible effectsはモナド変換子の代替として提案された*1。アクションを表すのに、Open unionsと呼ばれる特殊なデータ型を用いる。

data Union r v -- :: [* -> *] -> * -> *

inj :: (Functor t, Typeable t, Member t r) => t v -> Union r v

Unionは型レベルリストをパラメータとして取る。そのリストの要素に含まれていれば、inj関数を和型のコンストラクタのように使える。これをFreeモナドと組み合わせたモナドEffを導入し、liftいらずにしようという試みだ。

実装はextensible-effectsパッケージとして存在する。アクションがTypeableであることを要求する、データ型が不必要に再定義されているなど、やや引っかかりはある。特に、Typeableの制約ゆえに、多相なアクションはEffに持ち上げることができず、MonadStateのような関数従属性もない。計算量のオーダーの改善のため「慈悲なき反省」*2を起用しているが、動作は低速である。

より自由な作用

Oleg Kiselyov, Hiromi Ishiiにより、Operationalモナドをベースにした新しい実装が提案された*3。内部表現にはOkasakiの連結可能キューではなく二分木を使っており、パフォーマンスが向上している。

Hackageにはfreerがアップロードされ、freer-effectsに引き継がれた。速度は見違えるほど改善したものの、多相な型が持ち上げられない、型推論がうまくいかないと言った根本的な問題は解決されていない。

全部盛り

extensibleは拡張可能レコードのライブラリである。型に名前をつけて管理するため、多相型が推論の邪魔になることはない。この仕組みを拡張可能作用に応用すれば多相性の問題を解決できると考え、2015年の4月には基礎部分を実装した。「慈悲なき反省」を取り込んだ自前のOperationalモナドライブラリmonad-skeletonを、拡張可能ヴァリアントと組み合わせただけである。地味に画期的なmtlとの互換性もあったものの、あまり使うあてがなく、長時間放置していた。今年の2月になって急にモチベーションが向上し、まともな拡張可能作用のライブラリとして使えるようにAPIを整えた。

mtlの代替が基本の使い方である。まずはモジュールをインポートする。

import Control.Monad.State.Class
import Data.Extensible.Effect
import Data.Extensible.Effect.Default

アクションはmtlと互換性がある。lens演算子などももちろん利用可能だ。このような多相なパラメータをもつアクションを試してみよう。

increment :: (Num a, MonadState a m) => m ()
increment = modify (+1)

アクションを実行するには、Data.Extensible.Effect.Defaultモジュールのrun...DefleaveEffを使う。

runStateDef :: Eff (StateDef s ': xs) a -> s -> Eff xs (a, s)
leaveEff :: Eff '[] a -> a
*Main> leaveEff $ runStateDef increment 0
((),1)

ReaderT r (WriterT w (State s))に対応するモナドEff '[ReaderDef r, WriterDef w, StateDef s]で、覚えるのは難しくないだろう。実行するにはrunReaderDef, runWriterDef, runStateDefで、leaveEffで締めくくる。

好きな名前を与えることもでき、同じ型を持つ作用を複数持たせることもできる。その場合、Eff '["foo" >: WriterEff String, "bar" >: WriterEff String]のように書く。 名前付きのアクションはEffが名前に入っている。OverloadedLabels拡張を使うと簡単に作用名を指定できる(GHC 8.0の型推論器の制約上、Proxyが必要だった)。

test :: (Associate "foo" (WriterEff String) xs, Associate "bar" (WriterEff String) xs) => Eff xs ()
test = do
  tellEff #foo "Hello "
  tellEff #bar "hoge"
  tellEff #foo "world"
  tellEff #bar "fuga"

実行するときはTypeApplicationsを使う。

> leaveEff $ runWriterEff @ "foo" $ runWriterEff @ "bar" test
(((),"hogefuga"),"Hello world")

自前のアクションを持ち上げるにはliftEff、分解するにはpeelEff1を使おう。

liftEff :: forall s t xs a. Associate s t xs => Proxy s -> t a -> Eff xs a
peelEff1 :: forall k t xs a b r. (a -> b -> Eff xs r) -- ^ 結果を返す
  -> (forall x. t x -> (x -> b -> Eff xs r) -> b -> Eff xs r) -- ^ アクションを解釈する
  -> Eff (k >: t ': xs) a -> b -> Eff xs r -- ^ bは状態を表す変数

物好きならば、peelAction0を使ってみるのも面白いだろう。Action [a, b, c] ra -> b -> c -> E rを固有アクションとして持つ作用Eに相当する型で、自分でデータ型を定義することなく作用を扱える。decEffectsにGADTの定義を食わせることで、アクションをTHで自動生成できるぞ。

peelAction0 :: forall k ps q xs a. Function ps (Eff xs q)
  -> Eff (k >: Action ps q ': xs) a -> Eff xs a
decEffects [d|
  data Blah a b x where
    Blah :: Int -> a -> Blah a b b
    |]

type Blah a b = "Blah" >: Action '[Int, a] b
blah :: forall xs a b. Associate "Blah" (Action '[Int, a] b) xs
  => Int -> a -> Eff xs b

に変換される。

ベンチマーク

RWS相当のモナドベンチマークをした。 さすがに階層の浅いモナド変換子には及ばないものの、新しめの実装であるfreer-effectsの倍以上の速度で、なかなか良好と言えるだろう。

benchmarking rws/extensible
time                 11.63 μs   (11.33 μs .. 11.95 μs)
                     0.995 R²   (0.993 R² .. 0.997 R²)
mean                 11.79 μs   (11.49 μs .. 12.03 μs)
std dev              847.4 ns   (737.1 ns .. 984.8 ns)
variance introduced by outliers: 76% (severely inflated)
             
benchmarking rws/mtl
time                 909.5 ns   (890.9 ns .. 928.4 ns)
                     0.997 R²   (0.995 R² .. 0.998 R²)
mean                 896.4 ns   (882.1 ns .. 916.9 ns)
std dev              56.40 ns   (45.09 ns .. 79.70 ns)
variance introduced by outliers: 76% (severely inflated)
             
benchmarking rws/mtl-RWS
time                 721.7 ns   (713.3 ns .. 729.6 ns)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 721.5 ns   (714.2 ns .. 730.4 ns)
std dev              27.47 ns   (22.82 ns .. 38.35 ns)
variance introduced by outliers: 54% (severely inflated)
             
benchmarking rws/exteff
time                 150.5 μs   (145.3 μs .. 156.1 μs)
                     0.992 R²   (0.987 R² .. 0.995 R²)
mean                 148.5 μs   (145.3 μs .. 152.7 μs)
std dev              11.89 μs   (9.974 μs .. 14.74 μs)
variance introduced by outliers: 72% (severely inflated)
             
benchmarking rws/effin
time                 40.77 μs   (39.97 μs .. 41.87 μs)
                     0.994 R²   (0.991 R² .. 0.997 R²)
mean                 41.97 μs   (40.98 μs .. 43.27 μs)
std dev              3.509 μs   (2.887 μs .. 4.246 μs)
variance introduced by outliers: 78% (severely inflated)
             
benchmarking rws/freer-effects
time                 25.26 μs   (24.60 μs .. 25.86 μs)
                     0.992 R²   (0.983 R² .. 0.996 R²)
mean                 26.28 μs   (24.55 μs .. 31.05 μs)
std dev              8.954 μs   (2.011 μs .. 17.52 μs)
variance introduced by outliers: 99% (severely inflated)

Stackageのnightly-2017-07-31 (GHC 8.2)を使用した。

まとめ

既存の拡張可能作用の実装は、型とパフォーマンスの二つの問題を抱えていた。しかし、extensibleはその両方を解決し、拡張可能レコードも付いたお得なパッケージにまとまっている。実用的な局面にも十分に通用する使い心地を保証しよう。

リンク

*1:Oleg Kiselyov et al. http://okmij.org/ftp/Haskell/extensible/exteff.pdf, 2013

*2:Atze van der Ploeg and Oleg Kiselyov, Reflection Without Remorse, http://okmij.org/ftp/Haskell/zseq.pdf, 2014

*3:http://okmij.org/ftp/Haskell/extensible/more.pdf