りんごがでている

何か役に立つことを書きます

statisticsにt検定を実装しました

ちょっとHaskellstatisticsパッケージを見ていたら、統計的仮説検定に何故かt検定が無かったのでチョイチョイと実装しました。

https://github.com/bos/statistics/pull/66

masterの一歩手前のconfidenceブランチに取り込まれましたので、そのうち使えるようになると思います。

この実装で以下の3つの2標本検定が使えるようになります。

  • Student's t-test
  • Welch's t-test
  • paired samples t-test

詳細については、Wikipediaを参照下さい。

statisticsパッケージの検定のAPIがに統一感がなくてイケてない感じがするので、なにか思いついたらそちらも修正したいです。あとp値や統計量が得られないのはさすがに良くない気がします。

HaskellのFusionがあれば速度と抽象化を両立できる

データの分析をする際には配列やベクトルは欠かせないデータ構造です。 大体どの言語にも大体配列は用意されていて、そこにサンプルのデータ等を入れて統計量を計算したり関数に渡して回帰をしたりするわけです。 ベクトルという単位でデータの塊を扱うものの、実際のアルゴリズムではベクトル内の要素一つひとつを見ていって何か処理をしたり計算をすることが多いでしょう。 その際、命令型言語ではforループを陽に使って要素にアクセスすることになります。

簡単な例を見てみましょう。ベクトルv1v2内積を求める関数をC言語で書くと以下のようになります。

function dot(double* v1, double* v2, size_t n)
{
    double s = 0.0;
    for (int i = 0; i < n; i++) {
        s += v1[i] * v2[i];
    }
    return s;
}

特に難しいところはありませんね:)

ベクトル化された記法

しかし、大きなベクトルに対してこうして陽にループを書くことは、PythonやRではある種の「悪手」であると認識されています。 理由は単純で、PythonやRのインタープリタのループが遅すぎるため、NumPyのようなCやFortranなどで書かれた高速なライブラリに配列(実際にはPythonのオブジェクトが持つメモリ上のバッファへのポインタ)を渡して計算させるのが定石になっています*1

NumPyやSciPyではこうしたベクトルに対する関数や演算子が大量に用意されており、これらを組み合わせれば、明示的なforループを避けて簡潔に高速な計算ができるようになっているわけです。こうした操作をベクトル化(vectorized)された操作と言われています。 例えば、先程と同様2つのベクトルの内積を計算するならNumPyにnumpy.dot関数が予め用意されています。

import bumpy as np

v1 = np.array([1.0, 2.0, 3.0])
v2 = np.array([2.0, 3.0, 4.0])

print(np.dot(v1, v2))

ベクトルの要素ごとの積(*)と総和を求める関数を使えば、内積計算を以下のようにも書くことができます。

def dot(v1, v2):
    return np.sum(v1 * v2)

分散の計算

こうしたベクトル化された関数を組み合わせて標本分散(不偏分散)を計算してみましょう。 数式での定義は以下のとおりです。

f:id:bicycle1885:20140610232956p:plain

これを単純にNumPyを使ったPythonのコードに写してみましょう。(もちろん、NumPyには分散を計算するnp.var関数が用意されています!)

def var(x):
    return np.sum((x - np.mean(x))**2) / (np.size(x) - 1)

ベクトル化された関数を使えば、定義式をほとんどそのまま移すだけで、分散を計算する関数が作れました。

しかし、この方法には問題があります。それは、計算の途中に出てくる式の計算のために不要な一時配列が確保され、余計なメモリを食っていることです。 上の例では、x - np.mean(x)では、元の配列xと同じ大きさの配列が確保され、平均からの差分をそこに格納していく形になっています。(x - np.mean(x))**2ではさらに二乗の結果を格納する配列が確保されています。これらの一時的な配列は、本来分散を計算するためにはまったく不要なものです。 内積の例でも、np.sum(v1 * v2)のところでnp.sumに渡す一時ベクトルが新たに作られてしまっています。

def var(x):
    return np.sum((x - np.mean(x))**2) / (np.size(x) - 1)
#                  ~~~~~~~~~~~~~~
#                  ^
#                 ~~~~~~~~~~~~~~~~~~~
#                 ^
#                 余計なベクトルが2個作られている

Pythonのforループは遅くて使えないため、これを回避するためには、CやCythonで陽にループを書くハメになります。

#include <stdlib.h>
#include <stdio.h>

// Two-pass algorithm:
//   http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Two-pass_algorithm
double var(double* v, size_t n)
{
    double mean = 0.0;

    for (int i = 0; i < n; i++) {
        mean += v[i];
    }

    mean /= n;

    double ssd = 0.0;

    for (int i = 0; i < n; i++) {
        ssd += (v[i] - mean) * (v[i] - mean);
    }

    return ssd / (n - 1);
}

先ほどのベクトル化された計算と比べると、ループに展開したコードはかなり読みにくく、定義式との対応がわかりづらくなってしまいました。

ちなみに、Juliaでは、マクロを使ってベクトル化された記法からループへと展開するライブラリDevectorize.jlがあります。

fusionを使って宣言的に書き、効率的なコードを吐く

宣言的なベクトル化された記法をしつつ、ループと同等の効率的な実行を可能にするのがfusionです。 fusionでは、中間にできてしまう一時的なベクトルをライブラリによる自動的なコードの書き換え規則とコンパイラによる最適化で排除し、効率的なコードを生成する技術です。 Haskellvectorパッケージでは、ほとんど意識する必要なくベクトル計算のfusionを行ってくれます。 unboxedな値を格納するベクトルを使うなら、Data.Vector.Unboxedモジュールをインポートして使います。ここでは見た目を簡潔にするため、Preludeの名前が衝突する関数を隠しています。

import Prelude hiding (sum, zipWith)
import Data.Vector.Unboxed

dot :: Vector Double -> Vector Double -> Double
dot v1 v2 = sum $ zipWith (*) v1 v2

v1 * v2ではなくzipWithを使ってる点が若干分かりにくいかもしれませんが、ループを書かずに宣言的に内積が定義できています。それでいて、実はこのdot関数は計算の中間データを保持するベクトルを作っていません!

fusionがどうやって動いているのか

実際にfusionがどのような仕組みになっているか簡単な例で見てみましょう。 ここでは、Stream Fusion - From Lists to Streams to Nothing at Allのサンプルの一部ををGHCで試せるように書いてみます。 これは、stream fusionというfusionの一例です。 vectorパッケージではVector型に対してfusionを行っていますが、ここではリストを使っています。

minimal stream fusion

例えば、map f . map gというコードは関数合成の結合則stream . unstream ≡ idという関係式から、

map f . map g ≡ (unstream . mapS f . stream) . (unstream . mapS g . stream)
              ≡ unstream . mapS f . (stream . unstream) . mapS g . stream
              ≡ ustream . mapS f . mapS g . stream

となります。ここで、streamunstreamが打ち消しあうことで、リストとStreamの変換が消えますが、これはGHCrewrite ruleによって実現しています。 さらに、GHCの最適化によりStepの生成も排除され、効率的なコードが吐かれるわけです。 リストに対するstream fusionのより詳しい実装は論文の著者等によるstream-fusionパッケージを参照してください。ただ、最近のGHCは既にリストののfusionをサポートしているため、上のコードやstream-fusionパッケージを使ったものは普通に書いたものと同等のパフォーマンスになりました*2

分散の計算、再び

分散の計算をvectorパッケージを使って書いてみましょう。 fusionの効果を見るため、わざと関数を分けて定義しています。

import Prelude hiding (sum, length, zipWith, map)
import System.Environment (getArgs)
import Data.Vector.Unboxed as V
 
-- | pairwise product
(.*) :: Vector Double -> Vector Double -> Vector Double
x .* y = zipWith (*) x y
 
-- | sample mean
mean :: Vector Double -> Double
mean v = sum v / fromIntegral (length v)
 
-- | deviations from the mean
deviation :: Vector Double -> Vector Double
deviation v = map (\x -> x - mean v) v
 
-- | vectorized square
square :: Vector Double -> Vector Double
square v = v .* v
 
-- | sum of squared deviations from the mean
ssd :: Vector Double -> Double
ssd = sum . square . deviation
 
-- | unbiased sample variance
var :: Vector Double -> Double
var v = ssd v / fromIntegral (length v - 1)

このようにかなり宣言的にプログラムを書くことができ、それぞれの関数は単独で使うことも、他の場所で部品として使うこともできるなど再利用性も極めて高いです。Cの方だと可能なのはせいぜい平均値を計算するmean関数をくくりだすくらいでしょうか。

パフォーマンス比較

大きい配列に対してパフォーマンスを比較しみましょう。 長さ100,000,000の配列に対してCのループを使った実装とパフォーマンスを比べてみます。 使用したコードは以下のリンクにあります。 Gist - variance

Haskell: 0.49s user 0.35s system 99% cpu 0.839 total
C:       0.48s user 0.33s system 98% cpu 0.815 total

Haskellの実装とCの実装とでほとんど同じ速度がでていますね。Haskellコンパイルには-fllvmLLVMのコードを吐くようにすると何割か速くなりました。

本当に一時データが割り当てられていないかも見てみましょう。 Doubleは8byteなので、長さ100,000,000の入力ベクトルに対して800,000,000バイト程度が必要になります。 以下のヒープに割り当てられた領域の大きさからも、不要な配列が割り当てられていないのが分かります。

% ./variance-hs $(cat n) +RTS -s -RTS

     800,121,472 bytes allocated in the heap
          10,104 bytes copied during GC
          44,312 bytes maximum residency (1 sample(s))
          21,224 bytes maximum slop
             764 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0         1 colls,     0 par    0.00s    0.00s     0.0001s    0.0001s
  Gen  1         1 colls,     0 par    0.00s    0.06s     0.0562s    0.0562s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.50s  (  0.72s elapsed)
  GC      time    0.00s  (  0.06s elapsed)
  EXIT    time    0.00s  (  0.06s elapsed)
  Total   time    0.50s  (  0.83s elapsed)

  %GC     time       0.0%  (6.8% elapsed)

  Alloc rate    1,610,816,342 bytes per MUT second

  Productivity 100.0% of total user, 60.0% of total elapsed

新しいfusion

このようにfusionは強力なツールですが、今までのstream fusionにはいくつか限界があります。 最後に、こうした制約を取っ払うために発案された2つのfusionを紹介しましょう。 実装の詳細に関しては、私の能力の限界を超えるため、興味のある方は元の論文を参照してください。

Generalized Stream Fusion

2つのベクトルを結合して新しいベクトルを作りたいことはよくあります。 しかし、既存のstream fusionでは一度に1つづつしか値を取り出せないため、ベクトルを塊として扱うmemcpyのような効率的なコピーができません。 また、同じ理由で複数の値に一気に操作をするSIMD命令も使うことができません。

しかしGeneralized Stream Fusionでは素朴なStreamをより柔軟なBundleという単位にまとめることでこれらの問題を解決してくれます。 2つのベクトルの内積を計算するベンチマークでは、SSEを使うようにしたCのコードと同等かそれ以上の速度を出しています*3

f:id:bicycle1885:20140610233645j:plain

Generalized Stream Fusionでは、既存のHaskellのコードをほとんど変更することなく、合成可能な再利用性を保ったまま高速化できるのが魅力です。 この機能はvectorパッケージ上に実装されています。 現在OpenBLASやEigen3などの数値計算ライブラリと同等のパフォーマンスは出せていませんが、開発が進めばこれらのライブラリに迫るものができるかもしれません。

Data Flow Fusion

もう一つのstream fusionの拡張が、Data Flow Fusionです。 元のstream fusionではベクトルの値を変換して別のベクトルなり集計値を計算する「消費者」は常にひとりだけに限られています。 しかし、1つのベクトルから複数の統計量を計算したりする分岐をしたいことが常です。 大きなベクトルを複数回ループすることはキャッシュの有効利用ができないため、1つのループにまとめるのに比べて不利になってしまいます。

以下のコードは入力ベクトル(vec1)の要素をすべてインクリメントし(vec2)、正数のみを集め(vec3)たものとその中の最大の数をタプルにして返す関数です。

filterMax :: Vector Int -> (Vector Int, Int)
filterMax vec1 =
  let vec2 = map    (+ 1) vec1
      vec3 = filter (> 0) vec2
      n    = foldl max 0 vec3
  in (vec3, n)

この処理は一度のループで実行可能なはずですが、stream fusionでは1つのfusionにできない処理のようです。また、複数のベクトルに対して同時にループを行うときにループカウンタが重複してしまいレジスタを無駄遣いしてしまうこともパフォーマンスを悪化させてしまいます。

こうした問題をベクトル長の変化やデータフローを解析する高度なfusionによって解決するのがData Flow Fusionです*4。 実装は、Repaの配列に対するGHCの最適化プラグイン(repa-plugin)として提供されているようです。 この最適化により通常のstream fusion(Stream)に比べてdata flow fusion(Flow)では大きく性能が向上し、人間が手でfusionしたCのコード(Hand-fused C)に迫るパフォーマンスの向上を実現しています。

f:id:bicycle1885:20140610233649j:plain

fusionは既に実用的な技術になっており、より強力になったfusionが使えるようになるのもそう遠くないかもしれません。

Haskellでデータ処理がしたい!

この記事はIIJの@さんの下で、アルバイトとして書いています。 最終的な目的はHaskellでの統計処理やデータ処理のツールを整備しようというものですが、その下調べをした内容をこの記事にまとめています。 ご意見などコメントいただけるとありがたいです。


今から3年前の2011年のICFPに、Emily G. Mitchell 氏のHaskellを使ったシミュレーションに関するExperience Reportが掲載されました。

[PDF] Functional Programming through Deep Time - Modeling the first complex ecosystems on Earth

このレポートでは筆者が行ったエディアカラ紀の生態系シミュレーションの実装に関してプログラミング言語の選択や、使った言語にどのような利点・欠点があったかが述べられています。 初めはRを用いていたようですが、実行速度とシミュレーションのコード修正をするのに問題があってHaskellを選択した経緯とそのときに感じたHaskellでデータ処理をする際の問題点はとても興味深いものでした。 筆者は元々Haskellの使い手だったわけではないようですが、夫があのNeil Michell氏であることもあってか、シュミレーションにはHaskellを使い、プロットなどを含むデータ処理にはRを使ったようです。

その中でRと比較したHaskellの利点として以下のようなことが挙げられています。

  • 構文が一貫していること
  • 純粋さと静的型付けのおかげでコードのリファクタリングが容易であったこと
  • 型システムのおかげで、デバッグが容易であったこと

しかし、Haskellまわりのツールには不満点もあるようで、

  • 異なるパッケージの似たようなデータ型で互いにデータを変換するのが困難であること
  • Haskellパッケージのインストールが難しいこと (RはGUIでパッケージをインストールすることもできる)
  • 標準ライブラリで統計量の計算やプロットができないこと

などが挙げられています。

現状Haskellの統計パッケージあたりがどういうのがあるか調べてみると、Haskell Wikiにあるのは、

の3つだけです。(hstatsは2008年で止まっている)

プロットに関しては、

といった感じです。正直、充実しているとは言い難い状況ですね。

現状の機能では大変なことを実感するには、簡単な具体例を考えてみれば分かりやすいでしょう。以下の例は、2012年のHaskell cafeにあったスレッドの一部を翻訳したものです。

練習として、GHCiを使って適当な浮動小数点数の表になっているCSVファイルを読み込んで、ある列と別の列の間で線形回帰をして、回帰直線と一緒に散布図をプロットしてみてください。残差の正規性もチェックしてみるといいかも。大きなデータも扱えるようにするには、bytestringとかattoparsecなんかも使う必要があるでしょう。x86_64のGHCiからhmatrix/gslの関数を使うと、セグメンテーションフォルトとかバスエラーになる既知のバグがあることにも気をつけましょう*1。 何か当たり前なことを見落としてるかもしれませんが、(データの)コンテナ・永続化・パース・統計・プロットをするのにどのパッケージを選ぶのにすっっごく時間がかかるでしょう。

[Haskell-cafe] Mathematics and Statistics libraries

確かにこれをHaskellでやるのはちょっと考えてみただけどもやりたくない感じですね。 まずCSVのパースなのでcassavaあたりを使うといいのでしょうか。cassavaのData.CSVモジュールを見るとdecodeというのがあるのでこれを使えば良さそうですね。でも引数がByteString型なのでbytestringパッケージのData.ByteStringモジュールをインポートしてファイルを読む必要がありますね。返り値はVector型なのでそれから必要な列を取り出して線形回帰すればいいのですが、Haskellで線形回帰をするライブラリを探してぐぐってみるとstatistics-linregがありますね。よし、これをcabalでインストールしてとかやってられません。 しかしRやPythonなら、慣れている人なら5分とかからずにやってしまうでしょう。 試しにRでやってみるとたった6行です。

library(ggplot2)  # ggplot2ライブラリを読み込む
data = read.csv("data.csv")  # ヘッダーつきCSVファイルを読み込む
data.lm = lm(y ~ x, data)  # 線形回帰 
plot(data.lm)  # 残差の正規性をQ-Qプロットでチェック
ggplot(data, aes(x=x, y=y)) + geom_point() + stat_smooth(method="lm")  # 試しにプロット
ggsave("data.png")  # プロットを画像ファイルにセーブ

入力のCSVファイル:

id,x,y
0,0.125,2.140
1,0.065.567
2,-0.079,3.115
3,-0.193,1.765
...

プロット:

f:id:bicycle1885:20140411183421p:plain

この簡潔さを可能にしているRの特徴として挙げられるのは、

  • 表データを扱う組み込みのデータ構造 (データフレーム)
  • データ処理のための組み込み関数 (read.csv(), lm() など)
  • プロットのためのライブラリ (ggplot2, latticeなど)

などでしょう。 Pythonでも組み込みの機能はRほどではないにしろ、データフレームにはpandas、データ処理にはnumpy/scipy/scikit-learn、プロットにはmatplotlibがあり、IPythonを使えばRと同様インタラクティブに処理可能になります。

これを真似て処理するデータを収めるコンテナを統一的に扱えるようにし、データ処理によく使う関数をひとつのモジュールをインポートするだけで使えるようにすれば、結構Haskellでもいけるようになるのではないでしょうか。 加えて、快適に使うために欲しいものとしては、ドキュメントがサクサク読めて、データを眺めたりプロットをはめ込めるRStudioやIPython notebookのような統合的対話環境があると嬉しいです。

これらの機能を整備したとして、Haskellを使う利点は何でしょうか。 先の論文の要旨も踏まえて私の考えを3点述べると、

  1. 静的な型付けによる安全性とメンテナンス性の向上
  2. データ並列による処理の高速化
  3. 入出力の抽象化とストリーミング処理

これらはRやPythonではそう簡単には実現できない特徴ですので、うまくデータ処理のニーズと合致すればとても魅力的なツールになるはずです。 最後に、データ解析者やHaskellerの方々の目線から、このような機能は必須だとか、Haskellのこのライブラリを使うといいなどの意見をコメントいただけるととてもありがたいです。

*1:GHCの7.8.xでは修正されているようです。 https://twitter.com/kazu_yamamoto/status/454741146053255168

Haskell Tips (文字列編)

この記事はHaskell Advent 2012のための記事です。(遅れてすいません(ヽ´ω`))

Haskellで実際にプログラムを書く上では、様々なパッケージにある型や関数を利用するのが不可避になります。 そういった便利ツールのうち文字列まわりについて調べたところを、Haskell最近始めたって人に紹介するのがこの記事の目的です。Haskell詳しい方には新しい発見は無いかもしれません。ごめんなさい。

この記事では、主に文字列に焦点を当てていますが、そのうちまた別のテーマでも書こうと思っています。

なお、前提としてるバージョンはHaskell Platform 2012.4.0.0と、それに付随するGHCやパッケージです。 OSも、Mac OS XLinuxなどUNIX系の環境を想定しています。Windowsは持ってませんのでわかりません。ごめんなさい。

文字列

Haskellでは文字列の表現も色々あって、Haskellを始めたばかりの人はきっと混乱するでしょう。 自分も大混乱しましたよ。

Haskellで文字列を扱うのによく使われる型は大きく分けて以下の3つです。

  • String
  • ByteString
    • Strict
    • Lazy
  • Text
    • Strict
    • Lazy

ByteString型はbytestringパッケージで、Textはtextパッケージから提供されてます。 どちらもHaskell Platformに同封されてます。

ひとまず確認して行きましょう。

String

あんまり説明は要らないと思いますが、Stringはただの文字型Charのリストです。 なのでlengthやmapなどのリスト操作関数はそのまんま使えて便利ですし、自然な発想です。

Stringでは一文字で5ワードも占めるので、 メモリを喰いますし、速度もイマイチです。

でもStringはマルチバイト文字を扱えます。 以下のようなものはランタイムのロケールを考慮して、正しく出力されるはずです。

putStrLn "鬼"

そうそう、入出力のエンコーディングなどのロケール情報は、GHC.IO.Encodingモジュールの getLocaleEncodinggetLocaleFileSystemEncodingで取得できます。

import GHC.IO.Encoding

sample1 :: IO ()
sample1 = print =<< getLocaleEncoding

出力

UTF-8

他にもGHC.IO.Encodingにはエンコーディングを設定する機能などがあるようなので、この機能も必要があるかもしれません。


ByteString

「すごいHaskell」や「Read World Haskell」などを読まれた方はおなじみかと思います。bytestringパッケージで提供されているByteString型と関数で、効率良く文字列(というよりバイト列)を扱うことができます。

ByteStringが実際に収めているデータはWord8(8bitの符号なし整数)型なので、それより大きい要素を収めようとすると問題があります。マルチバイト文字など8bitに収まらないデータがそうです。

ByteStringには、実は同名の2つの型があります。 ひとつはData.ByteString.Internalモジュールで定義されている正格評価のByteStringで、 もうひとつはData.ByteString.Lazy.Internalモジュールにある遅延評価のByteStringです。 内部的には、Lazyな方のByteStringは、StrictのByteStringをリストにしているだけです。

-- LazyなByteStringの定義
import qualified Data.ByteString.Internal as S
data ByteString = Empty | Chunk {-# UNPACK #-} !S.ByteString ByteString

正格と遅延の型を字面だけ見て組み合わせようとしても、型エラーが出るので気をつけましょう(`・ω・´) 外部のライブラリを使うときは、ByteStringとだけ書いてあってもどちらか分からないので、ソースを読むなり、HTML版のHaddockのリンク先を確認するなりしないといけませんね。

じゃあ、これらの型の相互変換はどうするのかというと、bytestringパッケージのバージョン0.10.0.1では、 toStrictfromStrictが、LazyとStrictを相互変換するための関数が定義されています。 それ以前のバージョンでは、これらの関数は自作することになります。 このへんの話は以下のリンクを参考にして下さい。

他に、Data.ByteStringにはモジュール名の末尾にChar8がつくData.ByteString.Char8とData.ByteString.Lazy.Char8もありますが、これらはByteStringが内部でもつWord8のデータとCharの相互変換をしてくれる関数を間にかませているだけなので、本質的には何も変わりません。変換の分のオーバーヘッドはありそうですが。

このへんの挙動をちょっと見てみましょう。

下のコードの頭にあるOverloadedStringsは、文字列リテラルIsString型クラスのインスタンスへと自動的に変換してくれます。 ですので、文字列リテラルに関しては、bytestringやtextパッケージで用意されているpack関数を明示的に呼ぶ必要はありません。

コメントでは文字に対応する文字符号化形式のコードを書いています。

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString.Char8 as B8

sample :: IO ()
sample = do
    -- '鬼':
    --   UTF-16: 9B3C
    --   UTF-8:  E9ACBC
    -- '<':
    --   ASCII: 3C
    B8.putStrLn (B8.singleton '鬼')

    -- '平':
    --   UTF-16: 5E73
    --   UTF-8:  E5B9B3
    -- 's':
    --   ASCII: 73
    B8.putStrLn (B8.singleton '平')

    B8.putStrLn (B8.pack "鬼平")
    B8.putStrLn "鬼平"      -- OverloadedStringsがなければ、この書き方は型エラー

出力

<
s
<s
<s

漢字などマルチバイト文字は、Char型としての文字リテラルではUTF-16エンコードされている様子です。 しかし、ByteStringは内部的にはWord8(8bit)単位でしか扱えないので、 ByteStringに変換する際に、CharのデータはWord8(8bit)に切り詰められてるのが分かると思います。

文字列リテラルで指定されたマルチバイト文字を無理やりByteStringで扱おうとすると、特にエラーも出さず間違った結果を返すので注意が必要ですね。 なので、ByteStringは文字列というよりは、生のバイト列を収めるデータ型と思ったほうが良いと思います。

IOを介すなどして外部から与えられたマルチバイト文字は、 エンコーディングなど考慮されずにそのままバイト列として扱えます。 なので、以下のようにユーザーの入力を受け取る場合は、入力がマルチバイト文字を含んでいても問題ありません。入力をそのまま吐いてるだけです。

sample :: IO ()
sample = do
    putStrLn "What is your name?"
    putStr "> "
    name <- B8.getLine
    B8.putStrLn $ "Hello, " `B8.append` name
    putStrLn $ (show $ B8.length name) ++ "-byte"

出力

What is your name?
> 鬼平
Hello, 鬼平
6-byte

バイト数がUTF-8エンコードしたときにあたる6バイトになっちゃってますね。 これでは文字数は正しく数えられませんし、文字境界も分からないのでgrepのようなことも出来ません。


Text

じゃぁこういったマルチバイト文字をバイト列でなく、ちゃんと文字列として扱うにはどうすればいいのかと言うと、textというパッケージがありまして、こいつを使うというわけです。

ちゃんと文字列として扱うとは、文字列の長さが正しく数えられるとか、特定の文字を探せるとかそういう話です。

textパッケージでは、文字列操作のためのモジュールとIOのためのモジュールが別のモジュール(Data.Text.IO)にあります。下のように、同じTという別名をつけてimportすると楽ちんです。

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.Text    as T
import qualified Data.Text.IO as T

sample :: IO ()
sample = do
    T.putStrLn (T.singleton '鬼')
    T.putStrLn (T.singleton '平')

    T.putStrLn (T.pack "鬼平")
    T.putStrLn "鬼平"       -- これもOverloadedStringsが必要

出力

鬼
平
鬼平
鬼平

良い感じですね(´ω`) Data.Text.IOではロケールを考慮してくれています。

先ほどのByteStringのときと同じサンプルも、Textなら大丈夫です。

sample :: IO ()
sample = do
    putStrLn "What is your name?"
    putStr "> "
    name <- T.getLine
    T.putStrLn $ "Hello, " `T.append` name
    putStrLn $ (show $ T.length name) ++ "-letter"

出力

What is your name?
> 鬼平
Hello, 鬼平
2-letter

ちゃんと文字数を数えています。バイト数じゃなくって。 でも、Textのlength関数の計算量はO(n)です(´・ω・`)

Data.Text.IOには他にファイルやHandleとText型のデータをやり取りする関数も用意されてます。

TextはByteStringとの相互変換も可能ですし、Lazyなバージョンもあります。 相互変換に必要な関数はData.Text.Encodingモジュールにあります。

利用できるエンコーディングは以下の3つです。

下の例では、マルチバイト文字をByteStringで表現して、decode系の関数がそのByteStringをバリバリ喰ってTextにガガッと変換してくれます。

ちなみに、任意のバイト列を作成したい時は、 以下の様に文字列リテラルの中でバックスラッシュ()と16進数を表すxで指定することができます。 10進数では、xは要りません。

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString          as B
import qualified Data.Text                as T
import qualified Data.Text.IO             as T
import qualified Data.Text.Encoding       as T
import qualified Data.Text.Encoding.Error as T

sample :: IO ()
sample = do
    -- '鬼':
    --   UTF-8:  E9ACBC
    --   UTF-16: 9B3C
    let oniUTF8    = "\xE9\xAC\xBC" :: B.ByteString
        oniUTF16BE = "\x9B\x3C"     :: B.ByteString -- ビッグエンディアン
        oniUTF16LE = "\x3C\x9B"     :: B.ByteString -- リトリエンディアン

    T.putStrLn $ T.decodeUtf8    oniUTF8     -- Output: 鬼
    T.putStrLn $ T.decodeUtf16BE oniUTF16BE  -- Output: 鬼
    T.putStrLn $ T.decodeUtf16LE oniUTF16LE  -- Output: 鬼

    -- エンディアンの間違い!!
    T.putStrLn $ T.decodeUtf16LE oniUTF16BE  -- Output: 㲛

UTF-8ではバイトオーダーの指定は不要なのですが、 UTF-16では必要で、バイトオーダーを間違えると別の文字として認識されていしまいます。 外部から受け取ったUTF-16エンコードされているはずのByteStringなどを、Text型に変換する際はバイトオーダーに気をつけましょう。

あと、外部から受け取ったデータなどをText型に落としこむ際には気をつけなければならないことがあります。

以下の例は例外を投げてしまいます。

T.decodeUtf16BE "\xD8\x00"

出力

"*** Exception: Cannot decode input: Data.Text.Encoding.Fusion.streamUtf16BE: Invalid UTF-16BE stream

これは、Text型が内部的にはUTF-16を利用していることが原因です。 UnicodeではU+D800~U+DBFFとU+DC00~U+DFFFの範囲の16bitをペア(サロゲートペア)にして、16bitだけでは表現しきれない文字を表現しています。 この範囲はUTF-16では表現しきれないので、decodeUtf16BEなどでは例外を投げます。 外部から与えられたByteStringをデコードするときは、この挙動に注意して例外を拾うか、 decodeUtf16BEWith関数など、デコードのエラーが生じた時の挙動を明示する関数を使うといいでしょう。

lenientDecodeを使うと、デコードできないものはコードポイントU+FFFDに置き換えられます。

T.putStrLn $ T.decodeUtf16BEWith T.lenientDecode "\xD8\x00"

他にもUTF-8に限ればutf8-stringというパッケージがあるようですが、使ったことはありませんので分かりません(ヽ´ω`)

blaze-builder

チャンクのサイズが...

ByteStringの説明のところで、LazyなByteStringはStrictなByteStringのリストだと説明しました。 だとすると、細かく作ったStrictなByteStringをたくさんつなげばLazyなByteStringを作る場合、結局細かいByteStringが連なったリストが出来上がりそうです。

下の例では、5バイトのByteStringを10個連結して、50バイトのLazyなByteStringを作っています。 それをまたチャンクに分解して、それぞれの長さを調べると、確かに5バイトのチャンクが10個連なってます。

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad
import Data.Monoid
import Blaze.ByteString.Builder           as B
import qualified Data.ByteString.Lazy     as BL
import qualified Data.ByteString.Char8    as BS


chunkSizes :: BL.ByteString -> [Int]
chunkSizes = map BS.length . BL.toChunks

concatByteString :: Int -> BS.ByteString -> BL.ByteString
concatByteString n = BL.fromChunks . replicate n

main = print . chunkSizes $ concatByteString 10 "xxxxx"

出力

[5,5,5,5,5,5,5,5,5,5]

5バイトずつのチャンクになって、これじゃァCharのリストだったStringと大して変わらんってことで、 ひとつひとつのチャンクサイズを広げて、うまいことLazyなバイトストリングを作ってくれるのがblaze-builderです。

blaze-builderではBuilder型を介して文字列の結合をO(1)で行い、LazyなByteStringを吐き出すときに大きなチャンクを提供してくれます。

blaze-builderで文字列連結をするため、blazeConcatByteString関数を加えた例が以下のコードです。

{-# LANGUAGE OverloadedStrings #-}

import Control.Monad
import Data.Monoid
import Blaze.ByteString.Builder        as B
import qualified Data.ByteString.Lazy  as BL
import qualified Data.ByteString.Char8 as BS


byteN :: Int -> BS.ByteString
byteN n = BS.concat $ replicate n "x"

chunkSizes :: BL.ByteString -> [Int]
chunkSizes = map BS.length . BL.toChunks

concatByteString :: Int -> BS.ByteString -> BL.ByteString
concatByteString n = BL.fromChunks . replicate n

blazeConcatByteString :: Int -> BS.ByteString -> BL.ByteString
blazeConcatByteString n = B.toLazyByteString . mconcat . map B.fromByteString . replicate n

main =
    forM_ [1, 10, 100, 1000, 5000, 10000] $ \x -> do
        let bs = byteN x
        putStrLn $ show x ++ "-byte:"
        putStr "no-blaze "
        print . chunkSizes $ concatByteString      10 bs
        putStr "blaze    "
        print . chunkSizes $ blazeConcatByteString 10 bs
        putStr "\n"

出力

1-byte:
no-blaze [1,1,1,1,1,1,1,1,1,1]
blaze    [10]

10-byte:
no-blaze [10,10,10,10,10,10,10,10,10,10]
blaze    [100]

100-byte:
no-blaze [100,100,100,100,100,100,100,100,100,100]
blaze    [1000]

1000-byte:
no-blaze [1000,1000,1000,1000,1000,1000,1000,1000,1000,1000]
blaze    [4080,5920]

5000-byte:
no-blaze [5000,5000,5000,5000,5000,5000,5000,5000,5000,5000]
blaze    [4080,32752,13168]

10000-byte:
no-blaze [10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]
blaze    [10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]

blaze-builderを使ってつなげたほうが、チャンクのサイズが大きくなって、連結リストの長さが短くなってますね。 こうしてチャンクのサイズを大きくすることで、キャッシュの利用を効率化したり、入出力に関わるシステムコールのオーバーヘッドを低減しているようです。

詳しいバッファ利用の戦略などについては、blaze-builderのhaddock作者のブログ記事を参考にして下さい。

これを利用して、HTMLやSVGなどを高速に構築するblaze-htmlやblaze-svgといったパッケージがあります。 WebアプリケーションフレームワークYesodなどでも使われていますね。

ベンチマーク

最後に、blaze-builderがどれくらい効くのが、ベンチマークをカジュアルに取ってみましょう!

ベンチマークにはcriterionを使ってます。Haskellベンチマークが簡単に取れて、ブラウザで見られる出力も得られます。

blazeを使用しない元々の連結操作と、blazeを利用した連結との両方の方針で文字列片をつなげて、ファイルに出力しています。 ついでに、Textに関してもByteStringと同様にベンチマークを取ってみました。

{-# LANGUAGE OverloadedStrings #-}

import Data.Monoid
import Blaze.ByteString.Builder           as B
import Blaze.ByteString.Builder.Char.Utf8 as BT
import qualified Data.ByteString.Lazy     as BL
import qualified Data.ByteString.Char8    as BS
import qualified Data.Text                as T
import qualified Data.Text.Lazy           as TL
import qualified Data.Text.Lazy.IO        as TL
import qualified Data.Text.Encoding       as T
import qualified Data.Text.Lazy.Builder   as T
import Criterion.Main
import System.IO (openTempFile)
import System.Directory (removeFile)


-- N-byteのByteStringを作る
byteN :: Int -> BS.ByteString
byteN n = BS.concat $ replicate n "x"

concatByteString :: Int -> BS.ByteString -> BL.ByteString
concatByteString n = BL.fromChunks . replicate n

blazeConcatByteString :: Int -> BS.ByteString -> BL.ByteString
blazeConcatByteString n = B.toLazyByteString . mconcat . map B.fromByteString . replicate n


-- N-文字のTextを作る
textN :: Int -> T.Text
textN n = T.concat $ replicate n "鬼"

concatText :: Int -> T.Text -> TL.Text
concatText n = TL.fromChunks . replicate n

blazeConcatText :: Int -> T.Text -> TL.Text
blazeConcatText n = T.toLazyText . mconcat . map T.fromText . replicate n


main :: IO ()
main = do
    -- 出力用の一時ファイル
    (tmpfile, tmph) <- openTempFile "/tmp" "bench_blaze"

    -- 1, 10, 50の大きさの単語を、10000個つなげる
    let samples = [1,5,10,50]
        wc      = 10000

    defaultMain $
        [ bgroup ("[bytestring] " ++ show x ++ "-byte words") [
              bench "no-blaze" $ BL.hPut tmph $ concatByteString      wc (byteN x)
            , bench "blaze"    $ BL.hPut tmph $ blazeConcatByteString wc (byteN x)
            ]
        | x <- samples ]
        ++
        [ bgroup ("[text] " ++ show x ++ "-letter words") [
              bench "no-blaze" $ TL.hPutStr tmph $ concatText      wc (textN x)
            , bench "blaze"    $ TL.hPutStr tmph $ blazeConcatText wc (textN x)
            ]
        | x <- samples ]

    removeFile tmpfile

上半分がByteStringで、下半分がTextです。

f:id:bicycle1885:20121224233049p:plain

ちっちゃい文字列片ほど、効果が大きいようですね。

ベンチマークの実行は以下の様な感じです。

% ghc -O2 bench_blaze.hs
% ./bench_blaze -o bench_blaze.html

出力は分かりやすさのため一部削ってます。

出力

warming up
estimating clock resolution...
mean is 1.488974 us (640001 iterations)
found 4828 outliers among 639999 samples (0.8%)
  3539 (0.6%) high severe
estimating cost of a clock call...
mean is 58.44394 ns (8 iterations)
found 1 outliers among 8 samples (12.5%)
  1 (12.5%) high severe

benchmarking [bytestring] 1-byte words/no-blaze
mean: 1.221033 ms, lb 1.214946 ms, ub 1.228679 ms, ci 0.950
std dev: 34.94729 us, lb 29.31052 us, ub 43.71415 us, ci 0.950

benchmarking [bytestring] 1-byte words/blaze
mean: 136.0696 us, lb 125.3679 us, ub 144.9379 us, ci 0.950
std dev: 49.58111 us, lb 39.05003 us, ub 60.22993 us, ci 0.950

benchmarking [bytestring] 5-byte words/no-blaze
mean: 1.321834 ms, lb 1.310183 ms, ub 1.337639 ms, ci 0.950
std dev: 68.97484 us, lb 54.09187 us, ub 95.68489 us, ci 0.950

benchmarking [bytestring] 5-byte words/blaze
mean: 743.6934 us, lb 709.6834 us, ub 775.6366 us, ci 0.950
std dev: 169.3327 us, lb 132.2535 us, ub 223.0841 us, ci 0.950

benchmarking [bytestring] 10-byte words/no-blaze
mean: 1.396986 ms, lb 1.387786 ms, ub 1.408378 ms, ci 0.950
std dev: 52.24961 us, lb 42.96288 us, ub 63.49543 us, ci 0.950

benchmarking [bytestring] 10-byte words/blaze
mean: 1.448711 ms, lb 1.383338 ms, ub 1.513390 ms, ci 0.950
std dev: 331.6004 us, lb 294.9020 us, ub 414.8301 us, ci 0.950

benchmarking [bytestring] 50-byte words/no-blaze
mean: 6.478227 ms, lb 5.424632 ms, ub 7.761446 ms, ci 0.950
std dev: 5.944880 ms, lb 5.028813 ms, ub 7.670362 ms, ci 0.950

benchmarking [bytestring] 50-byte words/blaze
mean: 7.454674 ms, lb 7.041077 ms, ub 8.173508 ms, ci 0.950
std dev: 2.719382 ms, lb 1.760055 ms, ub 5.017425 ms, ci 0.950

benchmarking [text] 1-letter words/no-blaze
mean: 3.269654 ms, lb 3.259670 ms, ub 3.282536 ms, ci 0.950
std dev: 58.06780 us, lb 46.70660 us, ub 75.66644 us, ci 0.950

benchmarking [text] 1-letter words/blaze
mean: 306.1035 us, lb 304.2076 us, ub 308.4018 us, ci 0.950
std dev: 10.65997 us, lb 9.045305 us, ub 12.66282 us, ci 0.950

benchmarking [text] 5-letter words/no-blaze
mean: 4.930164 ms, lb 4.542772 ms, ub 6.752361 ms, ci 0.950
std dev: 3.662762 ms, lb 177.2833 us, ub 8.698922 ms, ci 0.950

benchmarking [text] 5-letter words/blaze
mean: 1.524795 ms, lb 1.515778 ms, ub 1.535984 ms, ci 0.950
std dev: 51.46477 us, lb 43.33059 us, ub 64.69094 us, ci 0.950

benchmarking [text] 10-letter words/no-blaze
mean: 5.897089 ms, lb 5.879782 ms, ub 5.917257 ms, ci 0.950
std dev: 95.94202 us, lb 82.75690 us, ub 114.9103 us, ci 0.950

benchmarking [text] 10-letter words/blaze
mean: 3.982748 ms, lb 3.591212 ms, ub 4.620310 ms, ci 0.950
std dev: 2.510847 ms, lb 1.805720 ms, ub 3.784512 ms, ci 0.950

benchmarking [text] 50-letter words/no-blaze
mean: 21.43716 ms, lb 19.98548 ms, ub 27.01497 ms, ci 0.950
std dev: 13.20911 ms, lb 2.446692 ms, ub 31.00659 ms, ci 0.950

benchmarking [text] 50-letter words/blaze
mean: 21.46007 ms, lb 20.58942 ms, ub 22.80350 ms, ci 0.950
std dev: 5.445815 ms, lb 3.780456 ms, ub 8.059161 ms, ci 0.950

ところで、最新のbytestring-0.10.2.0のパッケージを見ると、Builder関係のパッケージがbytestringから提供されてますね。 ドキュメントも、サンプルコードなどがあり充実してます。 textでは既にBuilderが入ってきてます。

まとめ

3種の文字列型と連結ライブラリのblaze-builderを見てきました。

  • Stringはマルチバイト文字も扱えてカジュアルに使えるけど長い文字列には向かない。
  • ByteStringは文字列というよりバイト列で、各種データをシリアライズするには便利。blaze-builderもあるし。
  • TextはStringのようにマルチバイト文字も扱えて、ByteStringのように効率のいい処理ができて嬉しい。

これらの実装もHaskellで書かれているので、ソースを読んでみればきっと面白い発見があると思いますよ(・ω<)。

何か間違いなどありましたら、Twitter宛@かコメント欄などで教えて頂けるとありがたいです。

モナドトランスフォーマー・ステップ・バイ・ステップ(Monad Transformers Step By Step)

著者のMartin Grabmüller氏に許可をいただきましたので、 Haskellモナドトランスフォーマーチュートリアルを翻訳したものを公開します。

タイポや誤訳、プログラムのミス等ありましたら、 Twitter宛@かコメント欄までご連絡頂けるとありがたいです。

元のテキストやプログラムは以下のリンクから得られます。

Monad Transformers Step by Step

  • [2012/12/19] 誤りを多数訂正しました。id:qtamakiさん、ありがとうございます。
  • [2014/6/19] 誤りを2点訂正しました。id:daimatzさん、id:hitotakuchanさん、ありがとうございます。

Monad Transformers Step by Step

Martin Grabmüller Oct 16 2006

概要(Abstract)

このチュートリアルでは、Haskellのプログラムに徐々に機能を追加していくためには、どのようにモナドトランスフォーマー(Monad Transformer)を利用したらよいかを説明します。

これはモナドトランスフォーマー自体の「実装」に関するものではありません。 エレガントでスッキリしていて、なおかつ強力なHaskellプログラムを書くために、いかにモナドトランスフォーマーを「利用」するかについてのチュートリアルです。

単純な式を評価する関数から始め、モナドスタイルに変えてから、モナドトランスフォーマーを構築しつつ、エラー処理、環境渡し、状態、ログ、入出力といった機能を加えていきます。

1 イントロダクション(Introduction)

このチュートリアルでは、Haskellモナドトランスフォーマーへステップ・バイ・ステップで紹介していきます。

モナドは、プログラムを組み上げていく上で、柔軟で拡張性を持つ非常にエレガントな手法です。 モナドHaskellのような遅延評価関数型言語ではとても興味深いもので、純粋関数型のプログラムに副作用を統合させることができます。 さらに、モナドを使ってプログラムを構築していくことで、ちょっとした定義があれば、色々なアルゴリズムの必要な記録処理や裏側の処理の多くを隠すことができ、注目してるアルゴリズムに集中することができます。

モナドトランスフォーマーモナドを使ったプログラミングをさらに便利にしてくれます。 違ったモナドや型やモナドを連結する関数のライブラリを提供してくれるので、必要なモナドトランスフォーマーを組み合わせて特製のモナドを作ることができます。 例えば、状態とエラー処理を備えたモナドが欲しいなら、StateTとErrorTふたつのモナドトランスフォーマーを選んできて組み合わせればよいのです。 このチュートリアルの目的は、シンプルな関数から始め、それをステップ・バイ・ステップで機能を拡張すべく色々とモナドを操って広げていく様を優しく紹介することです。 このチュートリアルモナドトランスフォーマーの概念の裏に潜んだ理論についてのものではありませんし、実装についてのものでもありません(うまいことモナドトランスフォーマーを使うのに必要なものは除く)。

ここでは、Haskellモナドクラスとかdo記法などといった、モナドを使ったプログラミングの機能や基礎については知っていることを想定しています。他のことは途中で追々説明していきます。

ここにあるHaskellのプログラムは現在のHaskell98標準のものではない機能を使っています。Control.Monad.Errorなどは標準ライブラリのモジュールではありません。 こうしたモジュールにある階層的なモジュール名も細かい実装もHaskell98の範疇ではありません。 しかしながら、こうした拡張は現在のGHC[1]ではちゃんとサポートされています。 プログラムはGHCのバージョン7.4.1で確認しています。

モナドトランスフォーマーのモジュールはMark P.Jonesの論文[2]にインスパイアされています。その中には、とても読みやすいMonadプログラミングのイントロダクションはありますが、このチュートリアルほどは実践的ではありません。

この文章は文芸的Haskell(Literate Haskell)のスクリプトからAndres Lo ̈hのlhs2TeXプリプロセッサを使って変換されています。 そのテキストはGHCで実行可能です。 文芸的Haskellのソースファイル Transformers.lhs は著者のウェブサイトhttp://www.grabmueller.de/martin/www/pub/Transformers.en.htmlにあります。

コンピュータを前にしてこのチュートリアルを読むのがベストでしょう。 Haskellの標準ライブラリやモナドトランスフォーマーのライブラリにある、いろいろな関数の説明を調べたり、型を調べたりできるようにです。 このチュートリアルを印刷して、ウェブブラウザでオンラインのライブラリのドキュメントを開いて、Transformersモジュール(あとで説明します)をロードしてghciで対話的に:type(もしくは:t)で型を確認しながら実行してみるのが一番でしょう。

1.1 プログラム例(Example Program)

実行する例として、シンプルなプログラミング言語インタープリタをこのチュートリアルを通して使います。 すべてのコードはTransformersというモジュールに収められ、次のようなコードが頭にあります。

module Transformers where
import Control.Monad.Identity
import Control.Monad.Error
import Control.Monad.Reader
import Control.Monad.State
import Control.Monad.Writer
import Data.Maybe
import qualified Data.Map as Map

Control.Monadで始まるインポートされたモジュールは、その中で定義されたモナドトランスフォーマーを使うときだけ必要となります。 Data.MaybeモジュールはMaybe a型の任意の値を扱うのに便利な関数を定義していて、Data.Mapモジュールは有限のマップを定義します。 これらは、環境(変数-値のマッピング)を小さなインタープリタの中で定義するのに使われます。

次のデータ型がその言語の中でプログラムをモデリングをするのに使われます。

type Name   = String                -- variable names (変数名)
data Exp    = Lit Integer           -- expressions (式)
            | Var Name
            | Plus Exp Exp
            | Abs Name Exp
            | App Exp Exp
            deriving (Show)
data Value  = IntVal Integer        -- values (値)
            | FunVal Env Name Exp
            deriving (Show)
type Env    = Map.Map Name Value    -- mapping from names to values (変数名から値へのマッピング)

Name型は標準のString型のただの別名です。 普遍的な文字列でなく、変数名についての話であることを明確にする時に使われます。 Expデータ型は、整数リテラル・変数・加算・λ式(抽象)・関数適用へのヴァリアントを持っています。 評価されるプログラムはExpデータ型からできていて、結果はValue型です。 Valueは整数か関数(クロージャ)です。 FunValの構成要素であるEnvは、λ抽象が評価される環境です。

モナドトランスフォーマーを用いる具体例は、上に示した小さな言語のインタープリタなので、まずは評価関数をつくることから始めます。 この関数はモナドを使っておらず、ある種の「参照実装」となっています。 インタープリタ関数eval0は、単純です。

eval0 :: Env -> Exp -> Value
eval0 env (Lit i)       = IntVal i
eval0 env (Var n)      = fromJust (Map.lookup n env)
eval0 env (Plus e1 e2)  = let IntVal i1 = eval0 env e1
                              IntVal i2 = eval0 env e2
                          in  IntVal (i1 + i2)
eval0 env (Abs n e)     = FunVal env n e
eval0 env (App e1 e2)   = let val1 = eval0 env e1
                              val2 = eval0 env e2
                          in case val1 of
                            FunVal env' n body -> eval0 (Map.insert n val2 env') body

整数リテラル(Lit)は、Value型に包まれてそのまま自分自身に評価されます。 変数(Var)は、その環境で束縛されている値に評価されます。 fromJust関数はMap.lookup関数がMaybeを返すので必要です。 この関数では、どこにもラムダ式で束縛されていない変数が使われてしまうと、エラーメッセージと共にプログラムは停止します。 加算(Plus)は単純に2つのオペランドを評価して、その和を返します。 加算のオペランドがが片一方でも数値にならなかったら、let式のパターンマッチングは失敗し、やはりエラーメッセージと共にプログラムは終了してしまいます。 抽象(Abs)は、評価される環境にを捉えて関数値に評価されます。 関数適用(App)は、最初に関数と引数を評価し、加算と同じように処理されます。 一番目の式は関数値に評価されなければならず、環境に従ってその内部が評価されます。 ここで使われている関数値を分解しているcase式は、また別のエラーを吐くかもしれません。 このチュートリアルの後の方では、エラーモナドを使ってエラーを扱い、エラーの扱いをもっと強力にしています。

eval0の定義はもう少し短くもできます。例えば、Appの時のlet式は冗長かもしれません。 しかし、ここでの定義は、後で定義されるモナド版にするのが簡単になります。

12 + ((λx -> x)(4+2))

この式は、このインタープリタを試すのにも使えますし、すぐに残りも定義していきます。

exampleExp = Lit 12 `Plus` (App (Abs "x" (Var "x")) (Lit 4 `Plus` Lit 2))

例えば、

> eval0 Map.empty exampleExp

とghciに入力すれば、答えは

IntVal 18

となります。

2 モナドトランスフォーマー(Monad Trasformers)

モナドトランスフォーマーを使う目的は、状態・エラー・環境といった計算の側面をコントロールすることです。 すでにあるプログラムをモナドを使って書きなおすのは少々面倒臭いですが、一度やってしまうとモナドが絡む部分を加えたり、削ったり、変更したりするのは比較的簡単です。

この節では、1.1節のプログラムをモナドを使って書き直し、データ型や関数定義を様々なモナドトランスフォーマーの型や関数を使って徐々に拡張していきます。

2.1 モナドスタイルに(Converting to Monadic Style)

モナドトランスフォーマーを使うには、関数をモナドスタイルで表現しなければなりません。 それはつまり、逐次処理をdo記法を使ったモナド操作で書き、関数の結果を示すためにreturn関数を使う必要があるということです。

まず、評価装置が定義されるモナドを定義します。 下のEval1 aIdentity a型の別名として定義します。Identityは、Control.Monad.Identityからインポートされてモナドで、想像しうる限り一番単純なモナドかもしれません。 Identityは、標準的なreturnや(>>=)をモナド操作の構築のために定義していて、runIdentity関数をそのような操作を実行するために追加で定義しています。 それ以外にはIdentityモナドは何もしません。 ある意味で、このモナドを「基礎」として使い、周りを別のモナドで包むこともできます。 可読性のため、ただrunIdentityを呼ぶためのrunEval1も定義しています。 runEval1はrunIdentityを呼び出すだけです。

type Eval1 a = Identity a
runEval1 :: Eval1 a -> a
runEval1 ev = runIdentity ev

Eval1モナドをもとにeval0関数をeval1として書きなおします。

eval1 :: Env -> Exp -> Eval1 Value
eval1 env (Lit i)       = return $ IntVal i
eval1 env (Var n)       = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval1 env (Plus e1 e2)  = do IntVal i1 <- eval1 env e1
                             IntVal i2 <- eval1 env e2
                             return $ IntVal (i1 + i2)
eval1 env (Abs n e)     = return $ FunVal env n e
eval1 env (App e1 e2)   = do val1 <- eval1 env e1
                             val2 <- eval1 env e2
                             case val1 of
                                FunVal env' n body ->
                                    eval1 (Map.insert n val2 env') body

まず注目すべきことは、LitとAbsの場合に結果を表すためにreturn関数を使っていることです。 (($)演算子は結合順位が低い関数適用で、主に丸括弧()を省くに使われます。) 次に、Varの場合にはfromJustはもう必要ありません。 これは、Map.lookupはどんなモナドの中でもfail関数を呼ぶだけで動くようになっていて、ここではこれがうまいこと当てはまるからです。 (Identityモナドのfail関数は例外を投げる一方、Maybeモナドのfail関数はNothingを返すので、異なるエラーメッセージが現れます。)

PlusやAppの場合は内部の式をdo記法で評価し、結果を変数に束縛しています。 Plusでは結果はreturnを使って返されますが、Appでは関数値は上のeval0関数のようにさらに識別されます。

このインタープリタを試すには、eval1をサンプルの式exampleExpに適用して得られたモナドのアクションを評価する必要があります。 これは前に定義したrunEval1を呼べば大丈夫です。

runEval1 (eval1 Map.empty exampleExp)

とすれば、

IntVal 18

となります。

要約すれば、return関数を使って関数の結果を返すことと、do記法や(>>=)や(>>)関数をつかってモナドアクションの逐次を行うことの2つからモナドへの変換は成り立っています。


NOTE

eval1の型は、以下のように一般化できます。

eval1 :: Monad m => Env -> Exp -> m Value

これは、returnと、do記法に隠された(>>=)以外には、どんなモナド操作も行っていないためです。 こうすればどんなモナドの文脈でもeval1を使うことができ、

runEval1 (eval1 Map.empty exampleExp)

とする代わりにghciで

eval1 Map.empty exampleExp

と書けます。 これは、IOモナドの内部で式を実行します。インタープリタは内部的にprint関数を使っていますが、この関数はIOモナドの内部でしか使えないためです。 これは嬉しいこともありますが、特定のモナドに固有の操作を使うことが多いでしょうし、特定のモナドに操作は縛られてしまいます。


2.2 エラー処理を加える(Adding Error Handling)

今まで見てきたように、現状の評価関数は部分的(partial)です。 例えば束縛されていない変数や型エラーがある式など、入力によってはエラーメッセージと共に止まってしまいます。 (訳注: 部分関数については、Partial Function Considered Harmfulが参考になります)

ローカルのモナドトランスフォーマーライブラリにあるErrorTモナドトランスフォーマーを使えば、Eval1モナドを基にしてEval2へ拡張できます。

type Eval2 a = ErrorT String Identity a

ErrorTのString型引数は例外の型で、エラーの状態を示すために使われる値です。 ここでは簡単のためにStringを使いますが、実際の実装ではコンパイラだとソースコードの位置だとか、ウェブアプリケーションだとタイムスタンプだとかがあると良いかもしれません。

Eval2モナド内での計算を実行する関数は、2つ異なる点があります。 ひとつ目は評価の結果がEither String a型で、Left sだとエラーが起きたことをエラーメッセージsで示し、Right rだと評価が成功したことを結果rで表します。 二つ目は、runErrorT関数を与えられた計算に対して呼び出し、Identityの計算が返され、今度はそれがrunIdentityを使って評価されるということです。

runEval2 :: Eval2 a -> Either String a
runEval2 ev = runIdentity (runErrorT ev)

さてもうeval1関数の型を単純に書き換えることができて、次のバージョン(eval2a)を示します。

eval2a :: Env -> Exp -> Eval2 Value
eval2a env (Lit i)      = return $ IntVal i
eval2a env (Var n)      = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval2a env (Plus e1 e2) = do IntVal i1 <- eval2a env e1
                             IntVal i2 <- eval2a env e2
                             return $ IntVal (i1 + i2)
eval2a env (Abs n e)    = return $ FunVal env n e
eval2a env (App e1 e2)  = do val1 <- eval2a env e1
                             val2 <- eval2a env e2
                             case val1 of
                                FunVal env' n body
                                    -> eval2a (Map.insert n val2 env') body

このバージョンは上で定義されたrunEval2関数を使って実行できます。 この関数をサンプルの式に適用すると、結果はRight構築子に包まれている点のみが変わっています。

runEval2 (eval2a Map.empty exampleExp) => Right (IntVal 18)

しかし残念なことに、正しくない式が与えられるとErrorTトランスフォーマーのエラー報告は使われません。 もっと有用なエラーメッセージを吐くためには改良が必要です。

eval2b :: Env -> Exp -> Eval2 Value
eval2b env (Lit i)      = return $ IntVal i
eval2b env (Var n)      = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval2b env (Plus e1 e2) = do e1' <- eval2b env e1
                             e2' <- eval2b env e2
                             case (e1', e2') of
                                (IntVal i1, IntVal i2) -> return $ IntVal (i1 + i2)
                                _                      -> throwError "type error"
eval2b env (Abs n e)    = return $ FunVal env n e
eval2b env (App e1 e2)  = do val1 <- eval2b env e1
                             val2 <- eval2b env e2
                             case val1 of
                                FunVal env' n body
                                    -> eval2b (Map.insert n val2 env') body
                                _   -> throwError "type error"

これで、正しくない式を評価しようとすると、Left構築子に包まれたエラーメッセージが出ます。 そして、評価結果に対してパターンマッチングをすることで、通常の結果とエラーの結果を区別することができます。

runEval2 (eval2b Map.empty (Plus (Lit 1) (Abs "x" (Var "x")))) =>
    Left "type error"

(訳注: 原文では runEval2 (eval2a Map.empty (Plus (Lit 1) (Abs "x" (Var "x")))) となっているが、著者の意図は恐らくeval2aでなくeval2b)

しかしちょっと待ってください! Map.lookupについてはどうでしょう? Nothingを返すかどうかを確かめて、適切なエラーメッセージを生成するべきではないでしょうか? 前述したとおり、Map.lookupは任意のモナドで結果を返しますし、Control.Monad.Errorモジュールはすぐに動くように必要な定義を提供しています。

runEval2 (eval2b Map.empty (Var "x")) =>
    Left "Data.Map.lookup: Key not found"

(訳注: containers-0.5.2.1の実際のData.Map.lookupの定義は、Maybeモナドを返すようになっている。なので、上記のエラーメッセージは、実際には Left "undefined variable: x" となる)

eval2b関数をもうちょっとよく調べてみれば、do式の内部のモナド結合ではパターンマッチングが失敗したときにfail関数を呼び出すということをうまく使うと、もっと短く(良く?)できることがわかります。 そして、今まで見てきたように、fail関数は思ったとおりに動いてくれます。

eval2c :: Env -> Exp -> Eval2 Value
eval2c env (Lit i)      = return $ IntVal i
eval2c env (Var n)      = maybe (fail ("undefined variable: " ++ n)) return $ Map.lookup n env
eval2c env (Plus e1 e2) = do IntVal i1 <- eval2c env e1
                             IntVal i2 <- eval2c env e2
                             return $ IntVal (i1 + i2)
eval2c env (Abs n e)    = return $ FunVal env n e
eval2c env (App e1 e2)  = do FunVal env' n body <- eval2c env e1
                             val2               <- eval2c env e2
                             eval2c (Map.insert n val2 env') body

この関数の難点は、エラーメッセージが"pattern match failure"(パターンマッチング失敗)としか言わないことで、どうしてパターンマッチングが失敗したのかについて具体的な情報は何もないということです。 ですので、もっと良いエラーメッセージが欲しいなら、自分でthrowErrorをする方が良いです。 これがエラー処理評価をする最終バージョンです。

eval2 :: Env -> Exp -> Eval2 Value
eval2 env (Lit i)       = return $ IntVal i
eval2 env (Var n)       = case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval2 env (Plus e1 e2)  = do e1' <- eval2 env e1
                             e2' <- eval2 env e2
                             case (e1', e2') of
                                (IntVal i1, IntVal i2)
                                    -> return $ IntVal (i1 + i2)
                                _   -> throwError "type error in addition"
eval2 env (Abs n e)     = return $ FunVal env n e
eval2 env (App e1 e2)   = do val1 <- eval2 env e1
                             val2 <- eval2 env e2
                             case val1 of
                                FunVal env' n body
                                    -> eval2 (Map.insert n val2 env') body
                                _   -> throwError "type error in application"

NOTE

Control.Monad.ErrorモジュールはthrowErrorで生じたエラーを捕まえるように、別の関数も提供しています。 それが、catchError :: m a -> (e -> m a) -> m aで、任意のエラーモナドに使えます。 局所的なエラー処理にもエラーを上位に渡すことにも使えます。


2.3 環境を隠す(Hiding the Environment)

評価関数の定義をもっといいものにする一つの方法は、すべての関数定義と呼び出しから環境を隠すことです。 環境が展開される場所は一カ所(関数適用)だけ、実際に使われる場所は二ヶ所(変数とラムダ式)だけなので、他の場所では環境を隠せばコードの量を減らすことができます。 これはリーダーモナドを実装するためにReaderTモナドトランスフォーマーを加えれば実現できます。 Readerモナドは、値をその下のすべての計算に渡します。 この値は内側の計算から読むことができ、入れ子になった計算の中では改変することもできます。 状態(State)モナド(2.4節で紹介されます)と異なり、カプセル化された計算は上位の計算で使われた値を改変することができません。

以前のモナド単にをReaderT構築子で包むことから始めます。

type Eval3 a = ReaderT Env (ErrorT String Identity) a

実行関数runEval3は、初期環境を与える必要があるので少し変更しなければなりません。 評価関数から環境引数を削ることが目的です。

runEval3 :: Env -> Eval3 a -> Either String a
runEval3 env ev = runIdentity (runErrorT (runReaderT ev env))

eval3 :: Exp -> Eval3 Value
eval3 (Lit i)       = return $ IntVal i
eval3 (Var n)       = do env <- ask
                         case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval3 (Plus e1 e2)  = do e1' <- eval3 e1
                         e2' <- eval3 e2
                         case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval3 (Abs n e)     = do env <- ask
                         return $ FunVal env n e
eval3 (App e1 e2)   = do val1 <- eval3 e1
                         val2 <- eval3 e2
                         case val1 of
                            FunVal env' n body
                                -> local (const (Map.insert n val2 env')) (eval3 body)
                            _   -> throwError "type error in application"

サンプルを実行するなら、以下のように評価してください。

runEval3 Map.empty (eval3 exampleExp)

現在の環境が必要になる場所では、Readerモナドの隠れた状態からask関数を使って引き出します。 関数適用の場合では、local関数が再帰的呼び出しの環境を変更するのに使われています。 localは(r -> r) -> m a -> m a型を持っていて、現在の環境から、第二引数にある入れ子になった計算で使われる環境へのマップをする関数を渡す必要があります。 この場合では、入れ子になった環境は現在の環境に直接依存していないので、const関数に渡すだけです。


NOTE

askに加え、asks関数が予め定義されていて環境から値へとマッピングする関数を取ります。 これは、レコードセレクター関数(record selector function)にasksを適用して環境のそれぞれの構成要素を取り出すのに使うこともできます。 (訳注:レコードセレクター関数とは、データ型をrecord syntaxで定義した際にコンパイラが自動的に作るフィールドの値を取得する関数のことです。)


2.4 状態を加える(Adding State)

重要なモナドの応用例として、純粋関数型のプログラムに変更可能(mutable)な状態を可能にすることが挙げられます。 これはStateモナドを用いればよく、初期状態の設定・現在の状態の問い合わせ・変更といった操作を提供してくれています。

例として、このインタープリタにプロファイリング機能を付け足したいとしましょう。 最も内側のモナド(Identity)をStateT構築子で包んで新しいモナドを定義します。 (StateモナドErrorモナドに関しては、後で見るように構築子の順番が問題になります。) 例では単純な整数値を状態として保持しますが、どんなデータ型の値でも可能です。 通常は、目下の仕事に必要十分な状態を、記録として保持することになります。

type Eval4 a = ReaderT Env (ErrorT String (StateT Integer Identity)) a

runEval4関数の返り値の型は変わります。 最終的な状態が評価結果(エラーか計算値)と一緒に返されるからです。 さらに、初期状態を追加の引数で渡し、例えば別の計算の最後の状態から再度計算を始めるなどができるように、柔軟性を持たせています。

runEval4 :: Env -> Integer -> Eval4 a -> (Either String a, Integer)
runEval4 env st ev = runIdentity (runStateT (runErrorT (runReaderT ev env)) st)

単純な例として、評価のステップ数を数えるだけにしたいと思います。 つまり、eval4関数を呼んだ回数です。 状態の変更は、すべて小さな補助的関数tickの中で起き、隠された状態を計算から取り出し、カウンターを増やして、状態を戻します。 この先の節で再利用するつもりなので、もちろんtickの型はEval4 ()ではありません。 ですので、中でtickが使われるモナドは状態モナド(訳注:この場合MonadState型クラスのこと)で、そのモナドの中で操作される状態は(+)演算子を使えるように数値にすると言うにとどめます。

tick :: (Num s, MonadState s m) => m ()
tick = do st <- get
          put (st + 1)

それぞれの場合でtick関数の呼び出しを加えれば、適用の回数を数えることができます。

eval4 :: Exp -> Eval4 Value
eval4 (Lit i)       = do tick
                         return $ IntVal i
eval4 (Var n)       = do tick
                         env <- ask
                         case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval4 (Plus e1 e2)  = do tick
                         e1' <- eval4 e1
                         e2' <- eval4 e2
                         case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval4 (Abs n e)     = do tick
                         env <- ask
                         return $ FunVal env n e
eval4 (App e1 e2)   = do tick
                         val1 <- eval4 e1
                         val2 <- eval4 e2
                         case val1 of
                            FunVal env' n body
                                -> local (const (Map.insert n val2 env')) (eval4 body)
                            _   -> throwError "type error in application"

サンプルを評価すると、

(Right (IntVal 18), 8)

と出ます。これは評価が成功して整数18を返し、簡約が8ステップだったということを表しています。


NOTE

Eval4モナドの型を次のように変える(StateTとErrorTを入れ替えた)と、モナドの解釈が変わります。

type Eval4' a = ReaderT Env (StateT Integer (ErrorT String Identity)) a

結果(エラーか否か)と状態を返す代わりに、エラーか結果と最終的な状態かを返します。 これは対応する実行関数の型からも分かるでしょう。

runEval4' :: Env -> Integer -> Eval4' a -> (Either String (a, Integer))
runEval4' env st ev = runIdentity (runErrorT (runStateT (runReaderT ev env) st))

最終的な状態には関与しないので、Readerモナドトランスフォーマーの位置は問題にはなりません。



NOTE

Stateモナドgets関数も提供しており、結果を返す前に状態に対して関数を適用します。 内部状態に関数を適用することによって状態を変更するmodify関数もあります。


2.5 ログを加える(Adding Logging)

ここで述べる道具箱にある最後のモナドトランスフォーマーWriteTです。 ある意味ReaderTの対になるものです。WriterTが提供する関数は、渡された値を用いるものではなく、計算結果に値を追加するものだからです。

type Eval5 a = ReaderT Env (ErrorT String
                           (WriterT [String] (StateT Integer Identity))) a

StateTの場合と同様に、結果を出力するものなのでWriterTはErrorTと干渉します。 ErrorTとWriterTの順番によって、エラーが起きたときに、結果が(訳注:Writerモナドの)値を返すかどうかが変わります。 書き出される値、は文字列のリストです。 WriterTモナドトランスフォーマーのドキュメントを読むと、書きだされた値の型はモノイド(Monoid)型クラスのメンバーに制限されることがわかるでしょう。 このことは、このクラスのメソッドは内部的に初期値を構成したり、書き出される値を合成したりするのに使われるため必要なことです。

実行関数は先ほどと同じように拡張されます。

runEval5 :: Env -> Integer -> Eval5 a -> ((Either String a, [String]), Integer)
runEval5 env st ev =
    runIdentity (runStateT (runWriterT (runErrorT (runReaderT ev env))) st)

評価関数では、評価中に遭遇した変数名を書き出すことによって、Writerモナドの使い方を説明しています。

eval5 :: Exp -> Eval5 Value
eval5 (Lit i)   = do tick
                     return $ IntVal i
eval5 (Var n)   = do tick
                     tell [n]
                     env <- ask
                     case Map.lookup n env of
                        Nothing  -> throwError ("unbound variable: " ++ n)
                        Just val -> return val
eval5 (Plus e1 e2) = do tick
                        e1' <- eval5 e1
                        e2' <- eval5 e2
                        case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval5 (Abs n e)   = do tick
                       env <- ask
                       return $ FunVal env n e
eval5 (App e1 e2) = do tick
                       val1 <- eval5 e1
                       val2 <- eval5 e2
                       case val1 of
                        FunVal env' n body
                            -> local (const (Map.insert n val2 env')) (eval5 body)
                        _   -> throwError "type error in application"

2.6 IOはどうすんの?(What about I/O?)

これまでのところ、ある重要な面を考慮していません。入力と出力です。 どのようにしてこれまでに開発してきたモナドの定義に、入出力を導入すればいいでしょうか。 IOモナドトランスフォーマーを定義することはできません。 なぜなら、HaskellのIO操作の実行は他の関数やモナドに勝手に入れ子にしてはならず、IOモナドでのみ可能になっているからです。 幸運なことに、モナドトランスフォーマーのライブラリは、私たちが組み上げてきたものに簡単にIO操作を導入する下地を提供してくれています。 単にIdentityの代わりにIOを使えばいいのです! これは、Identityが基になるモナドで、今まで見てきたように、このモナドのアクションを評価するrunIdentity関数は、いつでも一番最後に適用されていたからです。

type Eval6 a = ReaderT Env (ErrorT String
                           (WriterT [String] (StateT Integer IO))) a

runEval6が返す型は、IO構築子によって包まれています。 Eval6の計算を実行することは直接的に結果を出すのではなく、結果を得るには実行しなければならないIO計算を返します。

runEval6 :: Env -> Integer -> Eval6 a -> IO ((Either String a, [String]), Integer)
runEval6 env st ev
    = runStateT (runWriterT (runErrorT (runReaderT ev env))) st

eval6関数では、ちょっとしたひと手間でIO操作を行えます。 それには、liftIO関数を使って操作を呼び出す必要があり、これでIO計算を現在実行中のモナドに持ち上げることができます。 例として、整数定数が評価される度にプリントすることにします。(これが良い方法だとは思いませんが、要点を説明できますし、良いデバッグのテクニックになることもあります。)

eval6 :: Exp -> Eval6 Value
eval6 (Lit i)      = do tick
                        liftIO $ print i
                        return $ IntVal i
eval6 (Var n)      = do tick
                        tell [n]
                        env <- ask
                        case Map.lookup n env of
                            Nothing  -> throwError ("unbound variable: " ++ n)
                            Just val -> return val
eval6 (Plus e1 e2) = do tick
                        e1' <- eval6 e1
                        e2' <- eval6 e2
                        case (e1', e2') of
                            (IntVal i1, IntVal i2)
                                -> return $ IntVal (i1 + i2)
                            _   -> throwError "type error in addition"
eval6 (Abs n e)    = do tick
                        env <- ask
                        return $ FunVal env n e
eval6 (App e1 e2)  = do tick
                        val1 <- eval6 e1
                        val2 <- eval6 e2
                        case val1 of
                            FunVal env' n body
                                -> local (const (Map.insert n val2 env')) (eval6 body)
                            _   -> throwError "type error in application"

3 結論(Conclusion)

モナドトランスフォーマーは関数型プログラマーの持てる強力なツールです。 このチュートリアルでは、現在のHaskellの実装で利用できるモナドトランスフォーマーと、簡単なインタープリタを作るのにそれらをどうやって組み合わせるかを紹介しました。

ここでは、現在実装されているモナドトランスフォーマーを全てはカバーしていません。(例えば継続やリストのモナドトランスフォーマー) もっと情報を得るために、Haskellのウェブサイトにあるライブラリのドキュメントを読むこともおすすめします。

モナドトランスフォーマーを使うことで、今のアプリケーションでやりたいことを、一枚岩でお手製のモナドにまとめ上げ、様々なアプリケーションに特化したモナドをいとも簡単に作り出すことができます。

Happy hacking in Haskell!!

References

  • [1] GHC Developers. Glasgow Haskell Compiler Homepage. Available from: http://www. haskell.org/ghc, 2008. Last visited: 2008-10-07.
  • [2] Mark P. Jones. Functional programming with overloading and higher-order polymorphism. In First International Spring School on Advanced Functional Programming Techniques, vol- ume 925 of Lecture Notes in Computer Science, pages 97–136, B ̊astad, Sweden, May 1995. Springer-Verlag.

Haskellのパッケージ管理について調べてみた

Haskellやって1年ちょっと経つわけですが、Haskellで使うpackageの管理についてよく知らなかったので色々調べてみました。

対象としては最近Haskellを始めた方やpackage管理についてよく知らないという方向けです、 packageを利用する側からの説明なので、作るにはどうしたらいいかは書いてません(`・ω・´)ゞ

そして、やたら長いのです。

ちなみにghc-7.0.3で、OSはLinux Mintです。

packageって?

packageはHaskellのライブラリを構成する一つのまとまりで、packageはいくつかのmoduleをまとめています。

moduleはだいたい.hs拡張子のHaskellプログラム1ファイルと対応していて、module Foo.Bar whereとファイルの上の方に書いてあるFoo.Barがモジュール名です。

Haskell Platformに含まれる標準的なpackageはココを見てみましょう。 え、Haskell Platformを入れてない? 入れましょう(゚Д゚)

Haskell Platform

f:id:bicycle1885:20121007222819p:plain

右側にある haskell98-2.0.0.1 とかってヤツですね(・・)

packageはそのパッケージから利用できるmoduleがあって、あるパッケージのモジュールを使いたくなったらプログラムからimportするわけです。 どんなモジュールが使えるかは、次のようにghc-pkgコマンドを使うことで調べられます。 textパッケージから利用できるモジュールを調べてみると、

% ghc-pkg field text exposed-modules
exposed-modules: Data.Text Data.Text.Array Data.Text.Encoding
                 Data.Text.Encoding.Error Data.Text.Foreign Data.Text.IO
                 Data.Text.Internal Data.Text.Lazy Data.Text.Lazy.Builder
                 Data.Text.Lazy.Builder.Int Data.Text.Lazy.Builder.RealFloat
                 Data.Text.Lazy.Encoding Data.Text.Lazy.IO Data.Text.Lazy.Internal
                 Data.Text.Lazy.Read Data.Text.Read

となりますね。同じパッケージでも複数のバージョンがあるとそれも出てきます。

ghc-pkgコマンドは他にもいろいろ機能がありますが、それも追って紹介します。

cabalって?

Haskellのパッケージのメタ情報や管理などをしている一つのエコシステムです。

主な役者は、

  • Cabalパッケージ
  • cabal-installパッケージ
  • .cabalファイル
  • cabalコマンド

などです。

各パッケージのメタ情報は<package名>.cabalなるファイルに収められていて、ココに依存関係やらバージョンやらビルド方法など様々な情報が収められています。 Hackageにあるパッケージ群にはこのファイルが付属していて、こいつを使って管理されているようです。

Haskellのパッケージ管理は主にcabalコマンドを通して行います。 cabalコマンドはcabal-installパッケージが提供するCabalパッケージへのインターフェースです。 え?よくわからん?私もですъ(゚Д゚)

ちなみにcabal-installパッケージの依存先を見てみると、

f:id:bicycle1885:20121008004703p:plain

HTTPとかunixとかnetworkとかのパッケージに依存しててイカにも外部と通信してパッケージを取ってインストールしますよ〜ってな感じですね! もちろんCabalパッケージにも依存しているようです。

Cabalパッケージの依存関係はシンプルです。

f:id:bicycle1885:20121008005107p:plain

まぁHaskell Platformを入れていればcabalコマンドは使えるはずなので、特に問題ないはずです。 cabalを使えばHackageからパッケージをインストールしたり、自分の作ったパッケージをビルドしたりHackageへアップロードするのが簡単になります。助かります。

使い方

Hackageから特定のパッケージをインストールしてくるには、cabal installコマンドを使います。

が、そのまえに、Hackageにある最新のパッケージの情報とローカルの情報を同期させるため、

% cabal update

をしましょう。

それから、例えばconduitパッケージをインストールしたいなら、

% cabal install conduit

と打てば、conduitの最新版がインストールされます。 インストールするバージョンの指定もできます。

% cabal install conduit-0.5.2.4

各パッケージの情報は、

% cabal info conduit

とすればパッケージの説明や、現在インストールされているバージョンなどが見られます。 利用可能なモジュール名もここで表示されますね:-)


自分でHaskellのプロジェクトを作るには、

% cabal init

を使えば、対話的に自分のパッケージ管理のための.cabalファイルが生成されます。

自分のパッケージの依存関係を解決してインストールするには、.cabalファイルのあるディレクトリで

% cabal install

とすればOKです。Hackageから自動的に依存しているパッケージを集めてビルドしてくれます。 依存している必要なパッケージが一度入ってしまえば、次からはcabal buildをするだけです。

しかしこのcabalコマンドはなぜだかインストールしたパッケージを削除する機能が無いので、その辺使い勝手が良いcabを使うと良いかもしれませんねъ(゚Д゚)

cab: A maintenance command of Haskell cabal packages

他にも使うパッケージをプロジェクトで共有したくないよ〜って時はcabal-devが便利です。 パッケージの依存関係が他と干渉してメタメタになることはたまによくある(?)ことなので、こういうのも便利ですね!

他にもcabal-installの代替や補佐役のパッケージは色々ありますよ。

packageはどこに?

インストールして利用できるようになったはずのパッケージはどこにあるんでしょう? これは、% ghc-pkg listで一覧で出てきます。

% ghc-pkg list
/var/lib/ghc-7.0.3/package.conf.d
   Cabal-1.10.1.0
   GLUT-2.1.2.1
   HTTP-4000.1.1
   HUnit-1.2.2.3
   OpenGL-2.2.3.0
   QuickCheck-2.4.1.1
   ....
/home/kenta/.ghc/x86_64-linux-7.0.3/package.conf.d
   Cabal-1.14.0
   HUnit-1.2.4.2
   ListLike-3.1.6
   MissingH-1.1.1.0
   MonadCatchIO-transformers-0.3.0.0
   PSQueue-1.1
   QuickCheck-2.4.2
   SHA-1.5.0.1
   SafeSemaphore-0.7.0
   attoparsec-conduit-0.4.0.1
   ....

適当に% cabal installしまくってるとズラズラ〜っとたくさん出てきます。こんな感じでインストールされたパッケージの名前とバージョンが表示されますね。

上に表示された/var/lib/ghc-7.0.3/package.conf.dは、システムにインストールされたパッケージの情報を持っているディレクトリです。Haskell Platformをインストール先を指定せずインストールするとこんな感じのところに入ると思います。

その下の/home/kenta/.ghc/x86_64-linux-7.0.3/package.conf.dは、ユーザーの領域にインストールされたパッケージですね。% cabal installでインストールしたパッケージは普通こっちの管理下に入ります。なので普通に% cabal installするにはsudoは要らないわけです:-)


それでは、package.conf.d/ディレクトリの中を見てみましょう。

% ls /var/lib/ghc-7.0.3/package.conf.d
Cabal-1.10.1.0-e951c182da4a22a7b82c0f2e4be13b7b.conf
GLUT-2.1.2.1.conf
HTTP-4000.1.1.conf
HUnit-1.2.2.3.conf
OpenGL-2.2.3.0.conf
QuickCheck-2.4.1.1.conf
X11-1.5.0.0.conf
X11-xft-0.3.conf
array-0.3.0.2-143060371bda4ff52c270d1067551fe8.conf
base-4.3.1.0-91c3839608ff4d3ec95f734c5ae4f31c.conf
bin-package-db-0.0.0.0-03f52950478226c0334a7d7e83d56e17.conf
....

おぉ、パッケージの設定ファイルみたいなのが、たくさんありますね! package.conf.dってのはpackage configuration directoryの略でしょうかね。

一つ設定ファイルの中身を見てみましょう。中身は人間が読めるようになっています。 (長いので、一部省略)

% cat zlib-0.5.3.1.conf
name: zlib
version: 0.5.3.1
id: zlib-0.5.3.1-7e19941cbd00147a79723e25160ffc8b
license: BSD3
copyright: (c) 2006-2008 Duncan Coutts
(....)
exposed-modules: Codec.Compression.GZip Codec.Compression.Zlib
                 Codec.Compression.Zlib.Raw Codec.Compression.Zlib.Internal
hidden-modules: Codec.Compression.Zlib.Stream
import-dirs: /usr/lib/haskell-packages/ghc/lib/zlib-0.5.3.1/ghc-7.0.3
library-dirs: /usr/lib/haskell-packages/ghc/lib/zlib-0.5.3.1/ghc-7.0.3
hs-libraries: HSzlib-0.5.3.1
extra-libraries: z
extra-ghci-libraries:
include-dirs:
includes: zlib.h
depends: base-4.3.1.0-91c3839608ff4d3ec95f734c5ae4f31c
         bytestring-0.9.1.10-6aa1efbfa95d1689fc03d61e7c4b27c4
(....)

なるほど、「フィールド名: 内容」の形式で、バージョンやどんなモジュールが利用可能か、依存関係なども書いてありますね。 先ほど紹介した% ghc-pkg field <package名> exposed-modulesというヤツは、実はこのファイルのフィールドを指定して、それを表示させているだけでした。 つまり、% ghc-pkg field <package名> <フィールド名>となってます。

ですので、% ghc-pkg field zlib dependsとやれば、

% ghc-pkg field zlib depends
depends: base-4.3.1.0-91c3839608ff4d3ec95f734c5ae4f31c
         bytestring-0.9.1.10-6aa1efbfa95d1689fc03d61e7c4b27c4

と、どのフィールドでもフィールド名を指定してやれば見られるわけです。

実際には、.confファイルをキャッシュしているpackage.cacheファイルを見に行っています。straceがあれば、

% strace ghc-pkg field zlib depends 2>&1 1>/dev/null | grep open

などでわかりますね。

@さんに実際のコードの位置を教えて頂きました。ありがとうございます。( ;∀;)

Packages.lhs#L235

readPackageConfig :: DynFlags -> FilePath -> IO [PackageConfig]
readPackageConfig dflags conf_file = do
  isdir <- doesDirectoryExist conf_file

  proto_pkg_configs <- 
    if isdir
       then do let filename = conf_file </> "package.cache"
               debugTraceMsg dflags 2 (text "Using binary package database:" <+> text filename)
               conf <- readBinPackageDB filename
           return (map installedPackageInfoToPackageConfig conf)

  # (省略)

確かにpackage.cacheを読みに行ってますね!


そして、パッケージの実体がどこにあるのかというと、import-dirslibrary-dirsフィールドに書いてあるようです。 そこをfindで覗いてみると。。。

% find /usr/lib/haskell-packages/ghc/lib/zlib-0.5.3.1/ghc-7.0.3/ -type f -printf '%P\n'
HSzlib-0.5.3.1.o
Codec/Compression/Zlib/Raw.hi
Codec/Compression/Zlib/Stream.hi
Codec/Compression/Zlib/Internal.hi
Codec/Compression/Zlib.hi
Codec/Compression/GZip.hi
libHSzlib-0.5.3.1.a

おぉ、オブジェクトファイル(.o)やらインターフェースファイル(.hi)もありますね!

実際ghciで試してみると、

% ghci
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> :m Codec.Compression.GZip Data.ByteString.Lazy.Char8 
Prelude Codec.Compression.GZip Data.ByteString.Lazy.Char8> unpack . decompress . compress . pack $ "Compress me!"
Loading package bytestring-0.9.1.10 ... linking ... done.
Loading package zlib-0.5.3.1 ... linking ... done.
"Compress me!"

最後から2番目の行にある通り、ちゃんとzlibパッケージをロードして、リンクしてるらしいことがわかりますね。 *1


ココまではシステム(global)に入ったパッケージについて述べて来ましたが、ユーザー領域でも大体一緒のようです。 インストールされたパッケージは、先程調べたように/home/kenta/.ghc/x86_64-linux-7.0.3/package.conf.dにありました。 内容も一緒ですが、ここにはcabalで入れたものの情報が入ります。

コンパイル済みの実体は、~/.cabal/lib以下に同じように収まってますね。 ~/.cabal/binには、cabal installなどで入れたプログラムの実行ファイルがあります。cabal installでインストールしたプログラムを使うなら、ココへのパスを通しておきましょう:-)

先ほど紹介したcabal-devcabなどの実行ファイルも~/.cabal/binにありました。

それで、今までhackage.haskell.orgのレポジトリしか使ってませんでしたが、実はミラーがあります。 本家hackage.haskell.orgはちょくちょく落ちるので、ミラーを使ってみたりするのも良いかもしれません。

  • hdiff.luite.com
  • hackage.haskell.biz

はすぐ見つけられたのですが、他はよくわかりません(`・ω・´)ゞ

cabalコマンドでこれらのミラーを使うには、~/.cabal/configファイルのremote-remoを編集すれば、リポジトリを切り替えられます。 最初は本家の

remote-repo: hackage.haskell.org:http://hackage.haskell.org/packages/archive

になっているので、この行をコメントアウト(--)して、

-- remote-repo: hackage.haskell.org:http://hackage.haskell.org/packages/archive
remote-repo: hackage.haskell.biz:http://hackage.haskell.biz

とすればOKです。 試しに% cabal updateをしてみると、

% cabal update
Downloading the latest package list from hackage.haskell.biz

ちゃんとミラーに取りに行ってますね!

ちなみに、取ってきたパッケージの情報は、~/.cabal/packages/<リポジトリのホスト名>/00-index.tarに収められています。 本家レポジトリなら、~/.cabal/packages/hackage.haskell.ord/00-index.tarですね。

このtarファイルの中身は、% tar -tf 00-index.tarをしてみると、

% tar -tf 00-index.tar | head 
4Blocks/0.1/4Blocks.cabal
4Blocks/0.2/4Blocks.cabal
AC-Angle/1.0/AC-Angle.cabal
AC-Boolean/1.0.0/AC-Boolean.cabal
AC-Boolean/1.1.0/AC-Boolean.cabal
AC-BuildPlatform/1.0.0/AC-BuildPlatform.cabal
AC-BuildPlatform/1.1.0/AC-BuildPlatform.cabal
AC-Colour/1.1.1/AC-Colour.cabal
AC-Colour/1.1.2/AC-Colour.cabal
AC-Colour/1.1.3/AC-Colour.cabal

.cabalファイルがただひたすら入ってます。凄く...たくさんです...///

長くなってきたので一旦ここまで

なんだかやたらと長くなってきたので一旦ここまでにします。

そのうちある程度まとまったらまた書きます(^m^;)

Yesodチュートリアルの蛇足(3)

前回に引き続きYesodチュートリアルを先に進めていこう。

参考にしているチュートリアルはこちら
Haskell web programming


今回は3章Mirrorをやってみる。
こんな入力フォームに"Hello Yesod!"と打つと、そのテキストとテキストをひっくり返した文字列を結合した文字が表示される。
f:id:bicycle1885:20120214173519p:plain

("Hello Yesod!"と入力した)
f:id:bicycle1885:20120214173556p:plain

実装したコードを見てみると、Handler/Mirror.hsの中では次のように書かれている。

getMirrorR :: Handler RepHtml
getMirrorR = do
    defaultLayout $ do
        $(widgetFile "mirror")

これは、前回つくったEchoでも出てきているが、2つの"$"が登場している。
一つ目の$は関数に引数を適用するためのもの(中置演算子)で、カッコで代用できる。
だから、これでも問題ない。

getMirrorR :: Handler RepHtml
getMirrorR = do
    defaultLayout ( $(widgetFile "mirror") )

二つ目の$はTemplate Haskellにおいて構文木を接合するもので、$()の内部の構文木をその場につなぎあわせるものらしい。
その$()の中でwidgetFile関数が呼ばれていて"mirror"を引数としてとっている。すると、以下のテンプレートファイルを存在すれば読み込む。

  • templates/mirror.hamlet
  • templates/mirror.lucius
  • templates/mirror.cassius
  • templates/mirror.julius

今回はmirror.hamletとposted.hamletが読まれることになる。

WidgetというのはHTMLを"a monolithic tree of tags"ではなく"a number of distinct components in the page"と捉えるというものらしい。
詳しくはWidgetsに書いてる。

入力されたテキストは、POSTで渡され、postMirrorR関数内でpostedTextに束縛されている。
Hamletでは、呼ばれた関数内にある変数を自由に参照できるため、Hamletで入力されたテキストを受け取るには単純に#{postedText}とすればよい。
また、テキストを逆順にする関数reverseはHamlet側で利用する。
すなわち#{T.reverse postedText}となる。このTはHandlerの方で

import qualified Data.Text as T

となっていることから分かるようにData.Textモジュールであることを示している。
Hamletの#{...}内では、様々な関数が適用できることになる。