(cache)Haskell〇〇多すぎ問題

LugendrePublic
Haskell〇〇多すぎ問題
初心者が入門書を読んでさぁ書くぞとなったときにつまずくところのうちの一つが，同じようなライブラリが多すぎ問題である．
ということでそういうライブラリの話をしよう．

例によって例のごとく間違っていること書いてあるかもなので報告よろしく．

モナド変換子
Haskellで実用的なプログラムを書く上で避けて通れないものの一つにモナド変換子がある．こいつはなにかというと，簡単に言えば，モナドを合成してでかいモナドを作るやつである．人間がおおよそ使うであろうモナド変換子はライブラリで提供しているので，それらを組み合わせてお望みのモナドを作ろうとするわけだが，そこに立ちはだかるのが transformers と mtl である．
transformersとmtl
 transformers は lift  という下位のモナドのアクションをでかいモナドのアクションに持ち上げてくれるメソッドが定義された MonadTrans クラスと，各モナド変換子が定義されたパッケージである．しかし， MonadTrans は StateT や ReaderT などを持ち上げることができないため，これらがモナド変換子スタックの最上位であることを要求する．
一方で mtl は，モナド変換子スタック(要は上で言っているモナド変換子を組み合わせてできたでかいモナドのこと) m に対する型クラスとして， ask などの各種アクションを MonadReader などの MonadHoge 型クラスのメソッドとして定義しており， transformers の MonadTrans もreexportしている．これにより， MonadTrans の代わりに MonadState などを経由してアクションが呼べるため，先程の MonadTrans の制約に縛られずに自由にモナド変換子を使うことができる．

モナド変換子は transfomers で定義されているものと mtl で定義されているものがある．これは前述の MonadHoge を定義するのに MultiParamTypeClasses と FunctionalDependencies 拡張が必要なため，GHC(Huges)以外では使えないと言う問題がある．したがって， transformers は標準のHaskellでも使用できる MonadTrans とそれで必要十分なモナド変換子( MaybeT など)が， mtl では MonadHoge とそれのインスタンスとなるようなモナド変換子( ReaderT など)が定義されている．
実際はGHCを使わないということはほぼ無いはずなので，両方使って行くことになるだろう．

余談だが，具体的なモナド変換子スタックに言及せずパラメトリック(e. g.  m )にし，型クラス制約としてcomputationを表す(e. g.  MonadReader env m )ような設計手法をmtl styleと呼ばれており，現状のベストプラクティスとなっている雰囲気がある．自分でモナドを作る際はそのように計らうと良いだろう．

LazyとStrictってなんやねん問題
なんらかのライブラリのデータ型を使おうとすると Data.Hoge.Lazy だとか， Data.Hoge.Strict とかがあり，中身の関数や型は一見同じように見えて混乱する．これはいわゆる遅延データ構造か正格なデータ構造かの違いである．
遅延なデータ構造はメモリ効率が悪いので遅いが，値に undefined が持てたり，フィールドの一部がからでも動かすことができたりと便利である．モナドはメソッドの実装やアクションがlazyかstrictかという意味だったりするので注意しよう．
基本的に特別な理由がない限りStrictなデータ型を使うべきである．自分で定義するデータ型もそのようにしよう．

文字列多すぎ問題
プログラムを書く上で文字列を扱うことは避けて通れないが，ここにもいろいろなライブラリが潜んでいる(標準の文字列が糞すぎるとも言う)．

String, ByteString, Text
我々が慣れ親しんでいる文字列はを表す型は String である．これが [Char] の型シノニムであることはあまりにも有名である．遅延リストという糞効率の悪いものに Char を突っ込んで文字列を表現しているので，長い文字列を扱うと加速度的にパフォーマンスが悪くなっていく．
そこで，バイト列で文字列表そうぜ！というのが bytestring の ByteString である．これは内部的にはチャンクへのポインタとオフセットと長さのトリプルで，いかにも効率がよさそうである．このByteStringの1byteを Char に相互変換してくれるのが， Data.ByteString.Char8 である．O(1)で結合してくれる fast-builder などもあり，便利であるが，マルチバイト文字列を扱う場合はUTF-8にエンコードされるため，文字列の長さが正確に測れない，GHCの OverloadedStrings 拡張でリテラルを書くとUTF-16エンコードなので正しく読み込まれないなど，マルチバイトまで含めた文字列を扱うには貧弱である．
マルチバイト文字列も楽に扱いたい場合は， text の Text を使うと良い． ByteString と違い，2byteのバイト列を使った実装になっており，内部的にはUTF-16を第一級に扱っている．複数のエンコーディングにも対応している．

文字列を扱う際は，基本的に Text を使い，効率が要求される場面や単純にバイト列を扱いたい場合のみ ByteString を使うのが良いだろう．Alt Preludeである rio は基本的に文字列は Text として扱い，更に基本の関数の出力は Builder (メモリに書き込みする関数として文字列を持っておき，文字列の合成を関数合成に置き換えることでO(1)で結合するというテクニック)にするという徹底ぶりで高効率な文字列操作を実現している．使ってみるのもよいだろう． String に関しては，エラーメッセージなどごく限られた使用に留めるべきである(適当に Show のインスタンスを書くと効率が死ぬほど悪くなる問題)．

配列多すぎ問題
我々がよく使うデータ構造に配列がある．当然Haskellでも配列を使いたいわけだが，一体どうしたことか種類が多い．一体何が起きているんだろうか．

ArrayとVector
Haskellの配列として，大別して array に定義されている Array ( IArray )と vector に定義されている Vector がある．
どちらも内部表現は GHC.Exts に定義されている Array# というUnboxed値である(つまり生のメモリ表現．後述する)． Array は上界と下界と長さの情報が付加された Array# で， Vector はオフセットと長さの情報が付加された Array# である．
内部表現は上記の通りほぼ一緒だが，この２つはだいぶ違う．違いは以下のとおりである．
	 Array は(なぜか)インデックスの情報を付加することができる．
	 Array に比べ， Vector は様々な関数が定義されており，非常に便利である．
	 Vector はstream fusionという最適化により，関数を組み合わせたときの中間状態が極力発生しないようになっている．
	 Vector はGHC拡張が使われており，GHC以外では動かないが Array は標準のHaskellの範囲で動く
この中でもstream fusionの効果は馬鹿にできず， Vector にしただけで50倍はやくなったみたいなこともある．
GHCを使っているならとりあえず Vector を使っておけばよいだろう．

Boxed, Unboxed
Haskellは遅延評価や多相性を実現するため，値はヒープへのポインタとして表現されている．このような値をBoxed値と呼ぶ．一方で，GHCではポインタではなく生の値を格納することもでき，このような値をUnboxed値と呼ぶ．Unboxed値は単純にコンストラクタ，ポインタ分のメモリ消費(2word)を抑えられるだけでなく，参照によるオーバーヘッドもないのでかなり効率が良いが，遅延評価や多相性などを犠牲にしなければならない．
GHCは -O2 でコンパイルしていれば正格なフィールドはUnboxed値が入るように最適化され効率がよくなる．そういう意味でも前述した，特に理由がなければ正格なデータ構造を使う・定義するというのは大事である．

 Array や Vector には，このようなUnboxed値に特化した配列が用意されている．特にUnboxed Vectorは中身がバイト列である上，関数の一部が裏で PrimMonad を介してアセンブラレベルのGHCの組み込み関数に置き換えられているため，非常に高速に動作する．配列のような大きなデータは省メモリのためにも，できるだけUnboxedな Vector の使用を試みるべきだろう．自分で定義したデータ型を Unbox のインスタンスにしたい場合， vector-th-unbox にある derivingUnbox マクロが便利である．
とはいえ，何がなんでもUnboxedになるわけではないため，そういうときはおとなしくBoxedの Vector を使っておけば良い．

Immutable, Mutable
Haskellでは基本的にはすべての変数がimmutableであるように，配列も基本的にimmutableである．つまりは，(基本的には)配列の一部を変更すると，新しい配列が一から作られる．しかしそれでは流石に不便であるし，効率が悪いアルゴリズムを強いられるので， ST モナドや IO モナド越しに使えるMutableな配列も用意している．
とはいえ， Vector では実はそんなに出番がない．というのも，
	immutableな Vector の一部の基本的な関数は MVector を用いた実装になっている．
	 update のような破壊的変更の方が効率が良さそうな関数も，stream fusionによりコピーが走らないようになっている．
	GHCは特に破壊的変更に関する最適化を行わない要出典
という理由が挙げられる．破壊的変更をしたほうが見通しが良いときや実装しやすいとき，stream fusionが期待できないときにMutableな Vector を使うとよいだろう．また，ソートをしたいときは，Mutable Vectorを使う必要がある( vector-algorithms など)．
小技として， IORef や STRed がおそいので，singletonのMutable Vectorを可変参照の代わりにするなどというのがある．

exceptionとsafe-exception
mtl styleで例外処理に関する型クラス( MonadCatch など)を提供するライブラリに exception ,  safe-exception がある．
 safe-exception は，例外を投げるときに非同期例外かどうかを型情報に加えてから投げるため，これらによる分岐が可能であり，関数としても通常の catch は非同期例外を補足しないようにしている．非同期処理を行うのであれば， safe-exception が良い選択だろう．
bracket/finallyパターンで対応しきれないような，複雑なリソース管理に関しては， resource-t を使うのが良い．
詳しくは，Haskellの例外周りの話を参照のこと．