Hatena::ブログ(Diary)

あどけない話

2011-05-25

Haskellライブラリ入門 (2011年版)

この記事では、基本ライブラリである Prelude関数をだいたい理解した人が、次に知るべきライブラリを紹介します。自由自在にリストを使いこなせ、正規表現がなくてもプログラミングができるんだなと実感した人を対象にしています。

この記事のテーマは、脱リストです。リストはとても柔軟ですが、リストで表現されている文字列は、メモリーをたくさん消費しますし、なにより遅いのです。実用的なプログラムを書くためには、必要に応じて適切なデータ構造を使う必要があります。

containers

containersは、文字通りコンテナ型をいくつか集めたパッケージです。ハッシュ代替品やキューとして使えます。連想リストを使っているところは、すべて Data.Map などで置き換えることをお勧めします。

containers に入っているモジュールはすべて眺めましょう。そして、実装も読んでみましょう。(プログラミングコンテストに優勝するためには、Data.Sequence の理解は必須です。:)

Purely functional (永続的)な可変ハッシュで、今一番注目されいるのは hashmapです。これは、その内 containers に統合されると思います。詳しくは、The performance of Haskell containers package を読んで下さい。

Purely functional data structure の入門としては、20分でわかるPurely Functional Data Structuresが秀逸です。でも、Haskell の containers に入っているデータ型は、正格として定義されているので、あまり遅延しませんけど。。。

ByteString

バイト列あるいはASCII文字列を操作するには、bytestring を使います。

まず、OverloadedStrings という言語拡張を覚えましょう。これを使えば、ダブルクオートで囲んだ文字列を、ByteString リテラルとして扱ってくれるようになります。

ByteString は、リストと違ってパターンマッチできませんから、ガードを駆使して関数を定義することになります。リストでは length が O(N) なので使うべきではありませんが、ByteString では O(1) なので、どんどん利用しましょう。少し発想を変えてプログラミングする必要がありますが、すぐに慣れるでしょう。

ByteString には以下の四つのモジュールがあって、どれを使えばいいのか悩むかもしれません。

  1. Data.ByteString (正格 Word8)
  2. Data.ByteString.Char8 (正格 Char)
  3. Data.ByteString.Lazy (遅延 Word8)
  4. Data.ByteString.Lazy.Char8 (遅延 Char)

たとえば、Data.ByteString と Data.ByteString.Char8 で定義されている ByteString は同じ物です。単にインターフェイスが、Data.Word で定義されている Word8 を取るか、Char を取るかの違いです。変換のオーバーヘッドが気にならず、文字(Char)を便利に使いたいなら Data.ByteString.Char8 を使いましょう。少し不便だけれど、数値を指定して変換のオーバーヘッドをなくしたいなら Data.ByteString を使いましょう。

なお、OverloadedStrings のためには、Data.ByteString.Char8 の instance 宣言を読み込む必要があります。Data.ByteString を使いたいが、ByteString リテラルも使いたい場合は、以下のように指定する必要があります。

{-# LANGUAGE OverloadedStrings #-}

import Data.ByteString (ByteString)
import qualified Data.ByteString as BS
import Data.ByteString.Char8 () -- instance だけ読み込む

という訳で、違いを気にすべきなのは、正格 ByteString と遅延 ByteString です。使い方の結論を述べると、入力には正格 ByteString、出力は遅延 ByteString を用います。そういう風に使えてないとなると、あなたのコードはまだまだアマチュアなのです。

Text

Unicode 文字列を扱うには textを使います。利用感は ByteString と同じです。ただ、length が O(N) なので、利用は控えましょう。

Parsec

parsec は、パーサーライブラリの定番です。これさえ理解していれば、他のパーサーライブラリを理解するのは、とても簡単です。

Parsec は遅い反面、どこでどういうエラーが起こったか分かりますので、設定ファイルの解析など、ユーザに近いところを実装するのに適しています。

残念なことに、Parsec は現在混乱状況にあります。

parsec にはバージョン3相当の Text.Parsec とバージョン2相当の Text.ParserCombinators.Parsec が提供されています。バージョン3では、String に加えて、ByteString がサポートされたにも関わらず、Text はサポートされていません。

また、混乱を避けるためにパッケージが parsec2 と parsec3 に分離されたのに、Haskell Platform は parsec を採用してしまいました。

混乱はしばらく続くでしょう。

attoparsec

attoparsecは高速なパーサーライブラリです。エラー通知の機能は貧弱です。ですので、ユーザから遠いところで、高速処理をするのに適しています。attoparsec が対象とするのは ByteString です。Text を対象とした、attoparsec-text というライブラリもあります。

enumerator

Enumerator/Iteratee は Haskell コミュニティで今最も熱いパラダイムです。このパラダイムを使えば、一枚岩になりがちな IO を生産者消費者に分け、それらを合成することでプログラムを構成できます。

このパラダイムの入門には、使ってみよう EnumeratorEnumeratorは終了条件の検査からの解放だという記事をお勧めします。

Enumerator/Iterateeを実装するライブラリとしては、以下の3つがあります。

iteratee
Enumerator/Iterateeのパラダイムを考えた Oleg さんのライブラリ
enumerator
現在一番人気のあるライブラリ
iterIO
最新の洗練されたライブラリ。赤丸急上昇中

attoparsec は、enumerator と一緒に使うのがお勧めです。そのために、attoparsec-enumeratorattoparsec-text-enumeratorというパッケージがあります。

blaze-builder

文字列の連結は右結合にすると O(N) ですが、左結合にするとO(N^2)になってしまいます。そこで、文字列の連結を右結合にすることを保証するテクニックとして、差分リストが利用されてきました。

blaze-builderは、差分リストやその他のアイディアを融合させた高速な文字列生成ライブラリです。文字列の出力には、このライブラリを使いましょう。

mathfurumathfuru 2011/05/26 22:50 hackageDBのライブラリ群が多すぎて、何から手をつければいいのか困っていました。こちらのリストを指針に切り込んでいけそうです。ありがとうございます。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証