ステートマシン猛レース
ストリーム処理ライブラリはHaskellにおいて競争の激しい分野の一つだ。ストリーム処理ライブラリとは大雑把に言うと、IOなどの作用を絡めながら値の列(ストリーム)を生成したり、処理したりする構造を提供するライブラリである。多くのライブラリは、以下の3種の構造を定義している。
- 生産者(プロデューサー): IOなどのアクションを伴いつつ値を生成する。
- 消費者(コンシューマー): 多くの場合モナド変換子になっており、
await :: Consumer s m sのようなアクションを組み合わせ、値の列を処理するプログラムを書ける。 - 変換者(トランスデューサー): 入力を受け取りながら、出力もできる。
生産者と消費者が変換者の特殊な場合であるものも多い。
今回は、基本中の基本とも言える操作であるスキャンの速さを調べる。scan (+) 0は入力ストリーム[0,1,2,3, ...]を出力[0,1,3,6, ...]のように変換する。
iteratee, tubes, streaming, machinecell, io-streams, pipes, machines, conduit, boomboxと試作品のfeeders、predatorsパッケージをベンチマークした。ソースコードはhttps://github.com/fumieval/feeders/blob/all-bench/benchmarks/benchmark.hsにある。 ライブラリ数という点では、2017年現在最も網羅的なベンチマークだろう。
pipes
- 使用実績: ghc-mod, purescript
- 利点 速い、ドキュメントが豊富
- 欠点 終端、残余を扱えない
まずは人気のpipes。yieldとawaitをモナドで組み合わせる素直なインターフェイスが魅力で、scanの実装もわかりやすい。
ただし、runEffect以外の方法での分解はあまり想定していないのか、自分でPipeを分解するにはPipes.Internalモジュールをインポートしないといけない。その際はpipesの設計の理解が必須となる。
scan :: Monad m => (x -> a -> x) -> x -> (x -> b) -> Pipe a b m r scan step begin done = go begin where go x = do yield (done x) a <- await let x' = step x a go $! x'
変換に相当する値と、それを走らせる関数に分けてCriterionでベンチマークする。
sourceP :: Monad m => P.Producer Int m () sourceP = each [1..10000] drainP :: Pipe Int a Identity () -> () drainP p = runIdentity $ runEffect $ for (sourceP >-> p) discard main = defaultMain [ bench "pipes" $ whnf drainP (scan (+) 0 id) ]
10000要素を処理するのに179μsという結果が出た。一件あたり18ナノ秒はなかなか悪くないと言えるだろう。なおGHCは8.0.2で、CPUはIntel(R) Core(TM) i7-6700K CPU @ 4.00GHzである。
time 179.3 μs (177.9 μs .. 180.8 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 179.1 μs (178.4 μs .. 179.9 μs)
std dev 2.457 μs (2.043 μs .. 3.124 μs)
tubes
- 利点 インターフェイスが親しみやすい
- 欠点 極端に遅い
time 22.99 s (22.21 s .. 24.75 s)
0.999 R² (0.999 R² .. 1.000 R²)
mean 22.86 s (22.61 s .. 23.04 s)
std dev 269.8 ms (0.0 s .. 308.6 ms)
23「秒」という圧倒的な時間が目を引いたのはtubesだ。Freeモナドをベースにした基本を押さえたAPI、リストモナド相当のSourceに加えContravariantなSinkと第一印象は良いが、さすがに10万倍も遅いと実用的とは言いがたい。
scanT :: Monad m => (b -> a -> b) -> b -> Tube a b m x scanT f = go where go b = await >>= \x -> let !b' = f b x in yield b' >> go b' sourceT :: Monad m => Tube () Int m () sourceT = each [1..value] drainT :: Tube Int a Identity () -> () drainT h = runIdentity $ runTube $ sourceT >< h >< stop
streaming
使用実績: 不明
- 利点 速い
- 欠点 消費者がない
benchmarking scan/streaming time 77.40 μs (77.07 μs .. 77.74 μs) 1.000 R² (1.000 R² .. 1.000 R²) mean 77.17 μs (77.01 μs .. 77.41 μs) std dev 668.9 ns (552.8 ns .. 820.2 ns)
streamingはpipesの倍以上の速度が印象的だ。streamingには変換者や消費者に相当する構造はないため、やや不公平な比較かもしれない。
Stream (Of a)がaを生産するモナド変換子であり、これをリストのように扱う数々の関数が提供されている。
drainS :: (Stream (Of Int) Identity () -> Stream (Of a) Identity ()) -> () drainS h = runIdentity $ effects $ h sourceS sourceS :: Monad m => Stream (Of Int) m () sourceS = each [1..value] ... , bench "streaming" $ whnf drainS (S.scan (+) 0 id)
ストリーム処理ライブラリを使う動機はモナディックな消費であることが多いが、そうでない場合は選択肢となりうるだろう。
io-streams
使用実績: snap
- 利点 速い
- 欠点 何を書くにもIOを使わないといけない
time 87.93 μs (86.58 μs .. 89.68 μs)
0.996 R² (0.989 R² .. 1.000 R²)
mean 88.13 μs (87.08 μs .. 91.47 μs)
std dev 5.351 μs (1.913 μs .. 10.55 μs)
variance introduced by outliers: 63% (severely inflated)
io-streamsは使うモナドをIOに限定するという開き直った設計のパッケージだ。たかをくくっていたが、streamingに迫る速度が出ており侮れない。
import qualified System.IO.Streams as Is drainIs :: (Is.InputStream Int -> IO (Is.InputStream b)) -> IO () drainIs h = do i <- Is.fromList [1..value] i' <- h i o <- Is.nullOutput Is.connect i' o scanIs :: (b -> a -> b) -> b -> Is.InputStream a -> IO (Is.InputStream b) scanIs f b0 i = do r <- newIORef b0 Is.makeInputStream $ Is.read i >>= \case Nothing -> return Nothing Just x -> do b <- readIORef r let !b' = f b x writeIORef r b' return $ Just b'
machines
使用実績: 不明
- 利点 各種構造が透明で、拡張性に富む
- 欠点 Tee、Stackなどの発展形はAPIが乏しく、うまく合成できない
ekmett発のmachinesはまずまずの性能だ。
time 190.8 μs (190.1 μs .. 191.5 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 190.7 μs (190.2 μs .. 191.1 μs)
std dev 1.542 μs (1.366 μs .. 1.771 μs)
PlanTというCPSのモナドから変換器のMachineTを鋳造するというアプローチを用いている。複数の入力をサポートしているのも面白い。比較的習得は容易だが奥が深い。また、pipesと違い終端に対応できる。
sourceM = enumerateFromTo 1 value drainM :: ProcessT Identity Int o -> () drainM m = runIdentity $ runT_ (sourceM ~> m) , bench "machines" $ whnf drainM (scan (+) 0)
conduit
使用実績: Yesod
- 利点 ストリームの終端や残りをきちんと扱える
- 欠点 APIが複雑。オーバーヘッドがある
time 302.4 μs (301.5 μs .. 303.3 μs)
1.000 R² (1.000 R² .. 1.000 R²)
mean 302.1 μs (301.6 μs .. 302.8 μs)
std dev 2.029 μs (1.547 μs .. 2.515 μs)
かつて黄金時代を築いたconduitはmachinesよりも遅かった。しかし、ストリームの終端及び残余、リソースの解放などをサポートしていることを考えればかなり優秀だと言える。
import qualified Data.Conduit.List as C import qualified Data.Conduit.Combinators as CC drainC :: C.Conduit Int Identity a -> () drainC c = runIdentity $ (sourceC C.$= c) C.$$ C.sinkNull sourceC = C.enumFromTo 1 value , bench "conduit" $ whnf drainC (CC.scanl (+) 0)
この手のライブラリに依存しないような環境の変化が起こったものの、まだまだ現役だ。コンビネータの種類が非常に多く、ハードルが高いという難点もある。
iteratee
- 利点 ストリームの終端、残余はもちろんシークなども表現可能
- 欠点 遅い。設計が汚く、扱いが非常に難しい
使用実績: Tsuru Capital
最古参のiterateeはpipesの約20倍遅いという残念な結果となった。
time 3.392 ms (3.299 ms .. 3.502 ms)
0.995 R² (0.993 R² .. 0.998 R²)
mean 3.361 ms (3.325 ms .. 3.399 ms)
std dev 121.1 us (105.5 us .. 142.4 us)
variance introduced by outliers: 20% (moderately inflated)
実装もわかりやすいとは言いがたい。今あえてこのライブラリを選択する必要はないだろう。iterateeを使ったコードを保守するのは苦行そのものだ。
import qualified Data.Iteratee.Iteratee as I import qualified Data.Iteratee.ListLike as I scanI :: Monad m => (b -> a -> b) -> b -> I.Enumeratee [a] [b] m x scanI f = I.unfoldConvStream (\a0 -> I.liftI $ \case I.Chunk xs -> return $ mapAccumL (\a x -> let !r = f a x in (r, r)) a0 xs I.EOF _ -> return (a0, [a0])) sourceI :: I.Enumerator [Int] Identity a sourceI = I.enumList $ map pure [1..value] drainI :: I.Enumeratee [Int] [a] Identity () -> () drainI h = runIdentity $ I.run $ runIdentity $ I.run $ runIdentity $ sourceI $ h $ I.mapM_ $ const $ return ()
feeders
- 利点 iterateeの問題点を克服し、親しみやすいインターフェイスを持つ
- 欠点 まだまだ遅い
time 414.3 μs (409.7 μs .. 421.8 μs)
0.998 R² (0.996 R² .. 1.000 R²)
mean 413.9 μs (412.1 μs .. 421.0 μs)
std dev 9.814 μs (3.347 μs .. 22.63 μs)
variance introduced by outliers: 15% (moderately inflated)
Feederは、「消費者に供給する構造」として生産者を表現するiterateeの考え方を継承しつつ、よりまともなデザインを目指した試作品だ。
Eaterモナドが消費者、FeederがEaterを変換するモナドとして実装されている。
newtype Feeder s n m a = Feeder { unFeeder :: forall x r. Eater s n x -> (a -> Eater s n x -> m r) -> m r } killEater :: Monad m => Eater s m a -> m a sinkNull :: Monad m => Eater s m () feed :: Monad m => Feeder s n m a -> Eater s n x -> m (a, Eater s n x) type Rancher a b m = Feeder b m (Eater a m) (>-$) :: Monad m => Rancher a b m x -> Eater b m r -> Eater a m r scan :: Monad m => (b -> a -> b) -> b -> Rancher a b m () scan f b = lift await >>= \case Nothing -> return () Just a -> do let !b' = f b a yieldOn liftP b' scan f b' drainF :: Rancher Int a Identity () -> () drainF h = runIdentity $ killEater $ snd $ runIdentity $ feed sourceF $ h >-$ sinkNull sourceF :: Feeder Int Identity Identity () sourceF = yieldMany [1..value]
こちらもストリームの終端と残余を扱えるが、conduitにスピードに負けていては仕方がない。
predators
- 利点 iterateeやconduitと同等の実用的な表現力を、一風変わったシンプルな実装で実現
- 欠点 生産者を使いきって消費者を残すインクリメンタルな使い方はできない
PredatorはFeederとは逆に、生産者を捕食する構造として消費者を実装した。
prey :: Monad m => Predator s n m a -> Prey s n x -> m (Maybe (a, Prey s n x)) type Heterotroph a b m = Predator a m (Prey b m) (@->) :: Monad m => Prey a m x -> Heterotroph a b m r -> Prey b m (Maybe r) scan :: Monad m => (b -> a -> b) -> b -> Heterotroph a b m () scan f b = do a <- awaitOn lift let !b' = f b a lift $ yield b' scan f b' drainPd :: Heterotroph Int a Identity () -> () drainPd h = maybe () fst $ runIdentity $ prey Pd.sinkNull $ sourcePd @-> h sourcePd :: Prey Int Identity () sourcePd = yieldMany [1..value]
conduitと全く異なるアプローチでありながら、残余と終端を処理でき、同等の速度も出ているのでポテンシャルを秘めている。私のやる気が続けばさらなる進展があるかもしれない。ネーミングも気に入っている。
time 300.7 μs (299.2 μs .. 302.1 μs)
0.999 R² (0.998 R² .. 0.999 R²)
mean 314.9 μs (310.0 μs .. 321.2 μs)
std dev 19.03 μs (13.81 μs .. 23.15 μs)
variance introduced by outliers: 56% (severely inflated)
boombox
- 利点 高い柔軟性と高パフォーマンスを両立している
- 欠点 APIが非常に乏しい
ストリーム処理の大統一を目指して作ったライブラリboomboxはpipesよりも速い。
time 160.7 μs (160.1 μs .. 161.5 μs)
1.000 R² (0.999 R² .. 1.000 R²)
mean 163.1 μs (162.1 μs .. 164.1 μs)
std dev 3.382 μs (2.810 μs .. 4.125 μs)
variance introduced by outliers: 14% (moderately inflated)
生産と消費にTapeとPlayerTという専用の構造を用意し、変換器は両者を組み合わせて表現する。ストリームの残余処理、シークなどなんでも表現できるが、可能性を残しすぎたことが仇となりAPIが乏しい。Recorder Identity IdentityがPipeに相当する変換器で、IdentityをStoreに差し替えればシーク可能になり、当然通常のストリームからシーク可能なストリームへの変換器も定義できる。NonEmptyコモナドを使えば複数の世界線に分岐するようなストリームも表現できる。machinesと違い、どうカスタマイズしても必ず合成ができるのがポイントだ。
scanB :: (b -> a -> b) -> b -> Recorder Identity Identity m a b scanB f = go where go b = Tape $ await >>= \x -> let !b' = f b x in return (b', pure $ go b') sourceB :: Tape Identity Maybe Int sourceB = tap [1..value] drainB :: Recorder Identity Identity Maybe Int a -> () drainB h = maybe () (\(_,_,r) -> r) $ sourceB @.$ h >-$ forever await
パフォーマンスは良好なので、全ライブラリの統一を目指して研究を続けていきたい。
machinecell
- 利点 今のところ唯一のArrowベースのライブラリ
- 欠点 遅い
time 185.5 ms (184.1 ms .. 188.5 ms)
1.000 R² (1.000 R² .. 1.000 R²)
mean 184.2 ms (183.4 ms .. 185.3 ms)
std dev 1.176 ms (562.9 μs .. 1.702 ms)
variance introduced by outliers: 14% (moderately inflated)
machinecellはアロー変換子としてストリーム変換器を実装した異色のパッケージだ。これもなかなか速い、と思いきや単位がマイクロではなくミリで、pipesの1000分の1の速さだった。今後の改良に期待したい。
drainMc :: Mc.ProcessA (->) (Mc.Event Int) a -> () drainMc h = Mc.run_ (h >>> arr (const Mc.noEvent)) [1..value] , bench "machinecell" $ whnf drainMc (Mc.evMap (+) >>> Mc.accum 0)
まとめ
あまり凝ったことをしないならば、今のところpipesが無難だと考えている。しかし、終端処理、シークなどが絡むと、どのライブラリも困難に直面する。決着は未だついていない。
WindowsでのHaskell開発環境構築(2017年秋版)
身の丈に合わないと形容されても仕方ないようなハイスペックなPCを買った。開発環境は当然作り直すことになるので、その軌跡を残しておく。
MSYS2
まずはMSYS2を入れる。これでツールチェーンが揃い、minttyというターミナルエミュレータもついてくる。
$ pacman -Syuu $ pacman -Sy git
stack
Haskellのビルドツールであるstackのインストーラを入手する。処理系から依存パッケージまで無難かつ自動的に用意してくれるので便利だ。
ただしstackはMSYS2上ではうまく動作しない。設定ファイル(デフォルトではC:\sr\config.yaml)に以下の行を追加し、この問題を回避する。
skip-msys: true
マルチスレッドに強いと評判のRyzen 7を使っているので、並行ビルドで性能を存分に生かしたい。
ghc-options: "*": -j8
パスを通し、stack setupをすればGHCが使えるようになっているはずだ。
$ export PATH=$PATH:/c/Users/fumieval/AppData/Roaming/local/bin $ stack setup $ stack ghc -- -e 'let s = [Just "let s =",Nothing,Just "in putStrLn $ unwords $ map (maybe (show s) id) s"] in putStrLn $ unwords $ map (maybe (show s) id) s' let s = [Just "let s =",Nothing,Just "in putStrLn $ unwords $ map (maybe (show s) id) s"] in putStrLn $ unwords $ map (maybe (show s) id) s
困ったことに、パッケージをビルドしていると時々以下のようなエラーが出る。どうやらGHCの内部のAPIの呼び方が雑( #10731 (System.IO.openTempFile is not thread safe on Windows) – GHC)らしいので、後でなんとかしたい。
Configuring feeders-0...
C:\Users\fumieval\AppData\Local\Temp\: openTempFile: permission denied
(Permission denied)
エディタ
すっかりAtom派になった。language-haskellパッケージを導入すれば準備完了だ。
仮想環境
仕事の環境は基本的にUbuntu 16.04 LTSで統一されている。仕事だけでなく、ライブラリのメンテナンスのためにもLinux環境は手元に欲しい。
VirtualBox 5.1をインストールし、VMの作成に取り掛かる。このタイミングで時間や容量をケチる理由はないので、200GBの固定サイズのディスクを作成した。そして、プロセッサー数と使用率制限、ビデオメモリーは最大に。準仮想化インターフェイスはHyper-Vにし、仮想化支援機能は両方チェックを入れた。とりあえずネットワークアダプターはNATとする。
KDEが好きなのでKubuntuをインストールしたが、なぜか頻繁にクラッシュしてしまう。仕方がないのでPantheonというデスクトップ環境をインストールしてみた。見た目はなかなか悪くない。
sudo add-apt-repository ppa:elementary-os/stable sudo apt update sudo apt install elementary-desktop
もちろんSSHサーバ、Git、stack、Atomなどは入れてすぐ使える。私の会社の場合はChefで設定を管理しているので、knife bootstrapを実行すれば完成だ。
総評
昔に比べるとWindowsでの環境構築もだいぶ楽になった。
FRPクライシス
FRP(Functional Reactive Programming)は、リアクティブプログラミングと関数型プログラミングの性質を持つプログラミングパラダイムである。FRPは古典的FRPと矢矧のFRPに大別される。
古典的FRP
古典的(Classical)FRPは、非連続的な値の列Eventと、常に何らかの値を取るBehaviourの二種類の構造を導入したものである。 代表的な実装としてreactive-banana、euphoria、reflexなどが挙げられる。
Haskellにおいては、EventはIOを通じて非同期的に生成できる設計が多い。Eventはマップやフィルタリングができ、モノイドとして合成することもできる。なお、GenはFRPの構造を扱うのに要求されるモナドで、実装の都合上しばしば必要となる。Behaviourは現在の値を取り出せる他、HaskellならApplicativeのインスタンスにもなる。「読み取り専用のIO」とも言えるかもしれない。CFRPの構成要素をまとめると以下のようになる。
Eventを畳み込むaccumが肝で、Behaviorをサンプリングするapplyが心である。
矢矧のFRP
矢矧の(Arrowized)FRPは、値ではなく変換に着目し、値を変換する機構を導入する。Category及びArrowのインスタンスであるため、関数と共通の演算を持つ。実装はYampa、wiresなどがある。
(>>>) :: Category (~>) => (b ~> c) -> (a ~> b) -> a ~> c arr :: Arrow (~>) => (a -> b) -> a ~> b (***) :: Arrow (~>) => (a ~> b) -> (c ~> d) -> (a, c) ~> (b, d)
その実態は多くの場合ミーリマシンであり、状態を保持できる。表現する方法は色々あるが、例えば以下のような構造なら、入力に応じて次のMealyを決めるということができる。
newtype Mealy a b = Mealy { runMealy :: a -> (b, Mealy a b) }
(>>>)や(***)などを直接組み合わせるのは骨が折れるが、Arrow記法を用いることで比較的簡単に記述できる。arteryというライブラリでシンセサイザーを実装した例を紹介する。
sineWave :: Artery m (Float, Float) Float -- 周波数と位相を入力とし、正弦波を出力する genADSR :: Float -> Float -> Float -> Float -> Artery m Bool Float -- なめらかな立ち上がり・立ち下がりを持つエンベロープを生成する bell :: Artery m (Float, Bool) Float bell = proc (freq, gate) -> do env <- genADSR 0.01 0.4 0.2 0.4 -< gate m <- sineWave -< (64 * freq, 0) sineWave -< (freq * 2, m * env * 0.5)
入力を明示的に表現する必要があるが、CFRPに比べるとパフォーマンスにおいては優れている傾向がある。また、矢矧のFRPは固有の概念が少ないのも長所である。
FRPの問題点
両者の共通の利点でもあり落とし穴でもあるのは、状態を隠蔽できるというところだ。状態を完全に隠蔽することで組み合わせやすくなる場合もある一方で、一度FRPで構築したものは、状態が隠れているゆえに拡張性が乏しい。古典的FRPにおいては、入力への依存性も隠蔽されているため、特に注意が必要である。隠れた状態が増えるほど、プログラムの性質は複雑で把握するのが難しくなる。同時発生するイベントの処理も注意が必要である。
注意すべきこと
- 何でもFRPで書こうとしない: FRPは、異なった内部状態を隠蔽し、合成可能な共通の型によって扱うことを可能にする。しかし、この利点が活きないような場所に適用すれば、単に再利用性とパフォーマンスが犠牲になるだけである。
- ライブラリのインターフェイスをFRPに限定しない: APIをFRPに限定することは、FRPに起因する問題を回避する手段がないことを意味し、ユーザーにとって足枷となる。FRPのAPIは色々な操作をまとめることで成り立つが、その内部の操作もエクスポートされていれば柔軟な使い方ができる。よっぽどの信念がない限り、FRPはアプリケーションのコードだけにとどめ、ライブラリの実装では使わないのが得策だろう。
- FRPによって何が得られ、何が失われるか常に意識する: FRPでプログラムを表現することは、内部状態にアクセスする、文脈に依存せず動作するという性質を犠牲にして、状態の隠蔽、簡単な合成を可能にする。本当に自信がない限り、FRPを使うべきではない。
- FRPは、プログラムの注意点を増やし、決して減らすことはない: FRPが新たな構造と演算を導入する以上、冗長性をいくらか解消できても、本質的な複雑さをなくすわけではない。安全に使いこなすには仕組みの理解が不可欠であり、多くのCFRPライブラリのように、実装が隠蔽されている場合は特に気をつけるべきである。
FRPの代わりになりうるもの
- STM TVarを中心とする、状態を保持する構造に対する操作(トランザクション)を、STMという専用のモナドで記述する。トランザクションは状態が更新された時に実行されるようにでき、リアクティブな動作を表現できる。並行処理との親和性が高いのも魅力である。
- ストリーム処理ライブラリ 入出力と状態を扱うという面ではFRPとの共通点が多い。何もファイルやネットワークなどに限定する必要はなく、アプリケーションのロジックをストリーム処理ライブラリで記述するのもアリだ。
- objective objectiveはHaskellでオブジェクト指向を実現するライブラリである。オブジェクトは自然変換とミーリマシンの性質を併せ持っており、矢矧のFRPの発展形としても見ることができる。FRPと同様、安易な使用はアンチパターンである。
総評
私は仕事で古典的FRPを使ったコードを保守しているが、(私から見て)過剰に使われているため、かなりの重荷である。少しでもFRPを減らして保守性を高めるべく、繊維強化プラスチックのごとき決意を固めた。
快速のExtensible effects
extensibleは拡張可能レコードだけでなく拡張可能作用(extensible effects)も用意している。拡張可能作用は一時期Haskell界隈で話題になったものの、今では人気も下火になってしまった。新しいバージョンをリリースした今、拡張可能作用の動機と使い方について改めて紹介しよう。
難行の一次関数
Haskellでモナドをカスタマイズする方法としては、transformersのモナド変換子がよく使われている。モナド変換子は、モナドをパラメータとして取り、新たな能力を付与したモナドにする構造だ。例えば、StateT sはモナド変換子の一つである。任意のアクションm aはliftを使って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つのインスタンスを定義しないといけない。しかもMonadContとMonadWriterは単なる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...DefとleaveEffを使う。
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] rはa -> 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
generateの罠
vectorパッケージのData.Vectorにはgenerateという関数がある。
generate :: Int -> (Int -> a) -> Vector a
型から全てを知ることはできないが、だいたい想像通りgenerate n fは[f 0, f 1, f 2, ...f (n - 1)]からなるVectorを生成する。しかし、これは要素を評価はしない。生成されるのはあくまでサンクのVectorだ。
Prelude > import Data.Vector as V Prelude V> V.length $ V.generate 5 (const undefined) 5
vectorは速くて正格そうなイメージがあるが、ボックス化される方に関して、基本的に正格性は最小限なので注意しよう。どう工夫してもgenerateだけで正格なVectorは作れないので、generateMを使おう。
Prelude V> V.length $ runIdentity $ V.generateM 5 $ const $ pure $! undefined 5
Identityではダメなようだ…だが、継続モナドContを使うとうまくいく。
cont :: ((a -> r) -> r) -> Cont r a runCont :: Cont r a -> (a -> r) -> r
V.length $ flip runCont id $ V.generateM 5 $ \_ -> cont $ \k -> k $! undefined *** Exception: Prelude.undefined
継続最高。
波打たせるものの正体(エクステンシブル・タングル)
Haskell Advent Calendar 11日目
リアルワールドなHaskellerは、幾十ものフィールドを持つ大きなレコードをしばしば扱う羽目になる。モナディックにレコードを構築したい場合、RecordWildCards拡張を用いて以下のようにするのが定番だ。
import System.Random data Rec = Rec { foo :: String, bar :: Int, baz :: Double, qux :: Bool } makeRec = do foo <- getLine bar <- length <$> getLine baz <- readLn qux <- randomIO return Rec{..}
しかし、<-の右辺が大きい、フィールドの数が多い、といったリアルワールドにありがちな事象が掛け算されれば、定義は巨大になってしまう。
そこで登場するのがextensibleの拡張可能レコードである。たとえアプリカティブに包まれていようと、一発でレコードを鋳出すことができる。
extensibleについておさらいしよう。根幹となるのは拡張可能な積だ。
(:*) :: (k -> *) -- 顕現せし型 -> [k] -- 要素のリスト -> *
拡張可能な積(:*)は顕現せし型と要素のリストの二つの型パラメータを持つ。顕現せし型は、要素を現実、つまり種*の型に対応させる型である。例えば、T :* '[A, B, C]はタプル(T A, T B, T C)と等価となる。
普通のレコードとして使う場合、顕現せし型としてField Identityを帯びる。
type family AssocValue (kv :: Assoc k v) :: v where AssocValue (k ':> v) = v newtype Field (h :: v -> *) (kv :: Assoc k v) = Field { getField :: h (AssocValue kv) }
これにより、以下の型は前に定義したRecと等価になる。
type Rec = Field Identity :* ["foo" :> String, "bar" :> Int, "baz" :> Double, "qux" :> Bool]
レコードを作るには、各フィールドごとに関数を定義し、hgenerateForにほぼ直接渡すだけでよい。
インスタンス宣言でフィールドの型を二度書かないといけないのは少々面倒だが、これで拡張性を得られた。
{-# LANGUAGE TemplateHaskell, DataKinds #-} import Control.Monad.Trans.Class import Data.Extensible import Data.Functor.Identity import Data.Proxy mkField "foo bar baz qux" type Fields = ["foo" :> String, "bar" :> Int, "baz" :> Double, "qux" :> Bool] type Rec = Record Fields class MakeRec kv where make :: proxy kv -- kvを明示しないといけない -> IO (AssocValue kv) instance MakeRec ("foo" :> String) where make _ = getLine instance MakeRec ("bar" :> Int) where make _ = length <$> getLine instance MakeRec ("baz" :> Double) where make _ = readLn instance MakeRec ("qux" :> Bool) where make _ = randomIO makeRec :: IO Rec makeRec = hgenerateFor (Proxy :: Proxy MakeRec) (\m -> Field . pure <$> make m)
しかし、アクションに依存関係があるとこの方法は使えない。do記法とRecordWildCardsの定番スタイルでも、ステートメントの順番をうまく並べ替えなければならず、別の定義に切り分けるというのもそう簡単ではない。
そこでエクステンシブル・タングルという新しいアプローチを始めた。拡張可能な積h :* xsを構築するためのモナド変換子、TangleT h xsを導入する。
TangleT :: (k -> *) -- 顕現せし型 -> [k] -- 要素のリスト -> (* -> *) -- 礎のモナド -> * -- 結果の型
先ほどの例をTangleTを使うように変えると以下のようになる。liftを入れてTangleT (Field Identity) Fieldsを返している以外は特に違いはない。
class MakeRec kv where make :: proxy kv -> TangleT (Field Identity) Fields IO (AssocValue kv) nstance MakeRec ("foo" :> String) where make _ = lift getLine instance MakeRec ("bar" :> Int) where make _ = lift $ length <$> getLine instance MakeRec ("baz" :> Double) where make _ = lift readLn instance MakeRec ("qux" :> Bool) where make _ = lift randomIO
まずmakeを一か所に集める。型合わせのためにCompが使われている点に注意。
-- newtype Comp (f :: j -> *) (g :: i -> j) (a :: i) = Comp { getComp :: f (g a) } tangles :: Comp (TangleT (Field Identity) Rec m) (Field Identity) :* Rec tangles = htabulateFor (Proxy :: Proxy MakeRec) $ \m -> Comp $ Field . pure <$> make m)
これをレコードに変換するのがrunTanglesだ。最初の引数には先ほどのtangles、次は既知の値(ある場合)を渡す。既知の値はないのでwrench Nilを渡す。
-- runTangles :: Monad m -- => Comp (TangleT h xs m) h :* xs -- -> Nullable h :* xs -- -> m (h :* xs) makeRec :: IO (Record Rec) makeRec = runTangles tangles (wrench Nil)
このモナドの価値を決める必殺技とも言うべき固有アクション、それはlassoである。
lassoにフィールド名を渡すとその値が返ってくる。二度以上呼んでも実際の計算は一回しか行われないのがポイントである。
lasso :: forall k v m h xs . (Monad m, Associate k v xs, Wrapper h) => FieldName k -> TangleT h xs m (Repr h (k ':> v))
これにより、依存関係をいくら孕んでいようとも、簡単にレコードを構築できる。fooとbazが文字列として一致しているか確かめるコードはこんな感じになる。
instance MakeRec ("qux" :> Bool) where make _ = do str <- lasso foo x <- lasso baz return $ str == show x
しかし、なぜこんなものが必要になったのか――その動機は「波打たせるもの」にある。
メッセージフォーマット勉強会にて、このプログラムの存在について軽く触れた*1。監視対象はログを出力し、ネットワークを通じてオフィスのサーバーに配送される。ビューア(監視プログラム)はリアルタイムでログを読み取り、GUIとして表示するが、一つの問題が生じる。
「あるイベントが発生した回数」を表示したいとしよう。監視プログラムはそのイベントが出てくるたびに内部のカウンタを増やす。しかし、少し前の値を見ようとシークした途端、その値は無意味なものになってしまう。そういった値は監視対象がログに含めるという手もあるが、遠隔地にあり帯域も制限されているだけでなく、パフォーマンス上の要求から処理を増やしたくないため、なるべくこちら側で解決したい。そこで手を打つべく開発されたのが「波打たせるもの＜コラゲーター＞」である。
「波打たせるもの」は、監視対象と監視プログラムの中間に設置するプロセスであり、ログを読み取って監視プログラムのためのデータを生成する。出力はビューアに必要な情報(コラゲーションと呼ぶ)をすべて含んでおり、ストリームのどこにシークしても、イベントの回数などの累積的な値を正しく表示できる。結果として、ビューアはインターフェイスを除けば状態が不要になり、コードの簡略化にも繋がる。
波打たせるものが導入される前のログも読めなければいけないので、ビューアにもビルトイン・コラゲーターが内蔵されている。ビルトイン・コラゲーターは「ログとコラゲーションを読む」「部分的に非互換なコラゲーションを読む」「ログのみを読む」の3つのケースに対応する必要があり、ここがこのエクステンシブル・タングルの力の見せ所になる。
ログとコラゲーションが存在する場合、ビューアは何もする必要がない。そこでコラゲーションの有無で条件分岐するのではなく、runTanglesの二番目の引数にコラゲーションを渡す。こうすると、コラゲーションの一部が読み取れない場合も、必要な部分のみを計算できる。ログのみの場合は空っぽのレコードを渡せばすべて自力で賄う。
前回の記事*2でも触れたように、extensibleのレコードはデシリアライザを非常に簡潔に実装できる。また、顕現せし型を例えばField Maybeとすれば、部分的なデシリアライズも表現できる。エクステンシブル・タングルと組み合わせることで、パフォーマンスを損なわずに拡張性と互換性を持つロジックを記述できるのだ。
エクステンシブル・タングルが必要な場面は非常に限られていると思うが、ここぞというとき有効であることは約束する。他の言語ではなかなか真似できない、Haskellらしい表現力を活かしていきたい。
割とすぐに始められるextensibleチュートリアル(レコード編)
ごきげんよう諸君。今回はextensibleについて説明しよう。
extensibleはその名の通り、拡張可能なデータ構造を提供するライブラリである。具体的には、型レベルのリストによって特徴づけられる積と和を提供する。非常に残念なことに、GHC 8.0.1ではコンパイラのバグのせいでそもそもライブラリがビルドできない*1。来たる8.0.2では修正されているので、それを待つほかない。
とにかく、ここでは積の応用技である拡張可能レコードについて紹介する。使い方は簡単だ。まず使いたいフィールド名をスペースで区切ってmkFieldに渡す。
{-# LANGUAGE TemplateHaskell, DataKinds, TypeOperators, FlexibleContexts #-} {-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-} import Data.Extensible import Control.Lens hiding ((:>)) mkField "name collective cry"
すると、フィールド名を表す値がTemplate Haskellによって自動生成される。仰々しい型をしているが気にせず先に進もう。
$ stack ghci --package lens --package extensible > :load tutorial.hs ... > :t name name :: forall (kind :: BOX) (f :: * -> *) (p :: * -> * -> *) (t :: (Assoc GHC.TypeLits.Symbol kind -> *) -> [Assoc GHC.TypeLits.Symbol kind] -> *) (xs :: [Assoc GHC.TypeLits.Symbol kind]) (h :: kind -> *) (v :: kind) (n :: Data.Extensible.Internal.Nat). (Labelling "name" p, Wrapper h, Data.Extensible.Internal.KnownPosition n, Extensible f p t, Elaborate "name" (FindAssoc "name" xs) ~ 'Expecting (n ':> v)) => Data.Extensible.Internal.Rig.Optic' p f (t (Field h) xs) (Repr h v)
ここで、動物の名前と、群れの呼び方、ある場合は鳴き声の擬声語を含むデータ型を定義する。
type Animal = Record [ "name" :> String , "collective" :> String , "cry" :> Maybe String ]
Recordは、フィールドの名前と型のリストをパラメータとして持つレコードの型だ。名前と型のペアは:>で作る。
Record :: [Assoc k *] -> * (:>) :: k -> v -> Assoc k v
例としてハトとハクチョウを作ってみよう。
構築の方法はリストと同じと思ってよい。Nilは空のレコードで、(<:)で値を追加する。@=でフィールド名と実際の値を指定する。
-- (@=) :: FieldName k -> v -> Field Identity (k :> v) -- infix 1 @= dove :: Animal dove = name @= "dove" <: collective @= "dule" <: cry @= Just "coo" <: Nil swan :: Animal swan = name @= "swan" <: collective @= "lamentation" <: cry @= Nothing <: Nil
作っても使えなければ意味がない、しかし心配はいらない。実は、最初に定義したフィールド名はLensとしても使えるレンズ沼仕様になっているのだ。
> swan ^. name "swan"
Lensなので当然更新もできる。地上のハクチョウはbankと呼ぶのでそれを反映させてみよう。
> swan & collective .~ "bank" name @= "swan" <: collective @= "bank" <: cry @= Nothing <: Nil
動物を取り、その集団を表す句を返す関数を定義できる。
collectiveOf :: Animal -> String collectiveOf a = unwords ["a", a ^. collective, "of", a ^. name ++ "s"]
> collectiveOf dove "a dule of doves" > collectiveOf swan "a lamentation of swans"
collectiveOfはAnimal型を引数として取るが、実は以下のように一般化できる。
collectiveOf :: (Associate "name" String s, Associate "collective" String s) => Record s -> String
もはや引数はAnimalである必要はない。nameとcollectiveをStringとして持つなら、どんなレコードに対しても使える。これが拡張可能たる所以だ。
一見難解な仕組みに見えるが、実用するうえで必要なのはRecordおよび:>型とmkField、@=、<:、Nilだけであり、決して覚えるのが大変なものではない。同じ名前をどこでも使い回せる、lensとの相性がよいなどの性質があるので、従来のレコードの代わりに使うのも便利だ。
extensibleの拡張可能レコードは、ジェネリックな関数が書きやすいというメリットもある。以下のコードは、JSONのオブジェクトをレコードにするFromJSONのインスタンスだ。
これは、GHCのジェネリクスを用いた実装(332行)と比べるとはるかに短い。
{-# LANGUAGE TemplateHaskell, DataKinds, TypeOperators, FlexibleContexts, UndecidableInstances #-} {-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-} import Data.Extensible import Control.Lens hiding ((:>)) import Data.Aeson (FromJSON(..), withObject) import Data.Proxy import Data.String import GHC.TypeLits instance Forall (KeyValue KnownSymbol FromJSON) xs => FromJSON (Record xs) where parseJSON = withObject "Object" $ \v -> hgenerateFor (Proxy :: Proxy (KeyValue KnownSymbol FromJSON)) $ \m -> let k = symbolVal (proxyAssocKey m) in case v ^? ix (fromString k) of Just a -> Field . pure <$> parseJSON a Nothing -> fail $ "Missing key: " ++ k
ForallとhgenerateForがこのインスタンスの要になっている。Forall c xsは、「xsのすべての要素が制約cを満たす」という制約で、この場合、すべてのフィールドについて、名前は型レベル文字列、値の型はFromJSONのインスタンスであることを示している。hgenerateForはその制約を用いてレコードを一気に構築する関数だ。
Forall :: (k -> Constraint) -> [k] -> Constraint hgenerateFor :: (Applicative f, Forall c xs) => proxy c -> (forall (x :: k). c x => Membership xs x -> f (h x)) -> f (h :* xs)
Membership xs xはxがxsの要素であることを表す型である。ここでは、フィールド名をsymbolValとproxyAssocKeyでStringに変換するために使われている。Field . pureは具体的なフィールド名を指定せずにフィールドを構築する関数である。
> decode <$> fromString <$> getLine :: IO (Maybe Animal) {"name": "zebra", "collective": "dazzle", "cry": "whoop"} Just (name @= "zebra" <: collective @= "dazzle" <: cry @= Just "whoop" <: Nil)
リポジトリにはToJSONのインスタンスの例もある。
レコードに関しては、GHCのGenericsとは比べ物にならないほど簡潔に汎用的なインスタンスを記述できる。もし自前のクラスについてジェネリックなインスタンスを定義したいが、複雑で実装が難しいという場合は、ぜひextensibleを使ってみてほしい。
ここで紹介したのはextensibleの一部に過ぎない。次回は、レコードと対をなす構造、拡張可能ヴァリアントについて紹介したい。
