第4回　「取り出し可能な値」のみを持つListモナド

ITpro

2006.11.01

　前回のモナドの紹介に引き続き，今回は具体的なモナドの例について見ていきたいと思います。

　とはいっても，今回はまだIOモナドは取り上げません。たしかに，HaskellのモナドはIOモナドを意識して作られているため，IOモナドについて説明したほうがしっくりくる部分もあります。

　ただ，IOモナドはHaskellで使われている様々な技術を組み合わせたものになっています。いきなりIOモナドについて説明すると，どれがIOモナドの本質でどれがそうでないのかがわからなくなってしまいます。技術的な要請でしかないものを，IOモナドの性質と勘違いしてしまう危険性があるのです。

　こうした問題を回避するには，基礎的なものから段々と積み重ねて理解していくのがよいでしょう。前回，コンテナが持つ値には「取り出し可能な値」と「取り出し不可能な値」があると説明しました。今回は，「取り出し可能な値」のみを持つコンテナであるListを対象とするモナドについて紹介します。

前回の補足

　2006年10月11日にGHC6.6がリリースされました。WindowsやLinuxなどのパッケージが出ているため，すでに試した方もいるかもしれません。6.6では，噂になっていた多くの機能が（一部を除いて）追加されています（参考リンク）。

　こうした多くの変更のなかで，本連載の読者にとって直接関係のあるのは，6.6では処理系による暗黙的な種注釈が行われなくなったことでしょう（コード上に明示的に種注釈を宣言するための拡張機能は残っています，参考リンク）。

Prelude> :i Monad
class Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  fail :: String -> m a
        -- Defined in GHC.Base
instance Monad Maybe -- Defined in Data.Maybe
instance Monad IO -- Defined in GHC.IOBase
instance Monad [] -- Defined in GHC.Base

　とはいえ前回も述べた通り，種注釈があったほうがわかりやすい場合もあります。この連載では，必要だと思われるところではGHC6.4.2での出力を表示することにしたいと思います。

List型

　さて「取り出し可能な値」しか持たないというのは，どういうことでしょうか？これで3回目になりますが，まずはListの定義について見てみましょう。

Prelude> :i []
data [] a = [] | a : [a]        -- <wired into compiler>
instance Eq a => Eq [a]         -- Imported from GHC.Base
instance Monad []       -- Imported from GHC.Base
instance Functor []     -- Imported from GHC.Base
instance Ord a => Ord [a]       -- Imported from GHC.Base
instance Read a => Read [a]     -- Imported from GHC.Read
instance Show a => Show [a]     -- Imported from GHC.Show

　Listは，無引数のデータ構成子[]，または「型変数aの値」と「型変数aの値を持つリスト」を持つ中置データ構成子(:)で構成されているのがわかります。[a]は[] aの別名に過ぎないため，[a]は，[]またはa:[] a（つまり前から順にaと(:)と[] a自身）を取る再帰的定義の型――「再帰型（recursive type）」になっています。また，前回と前々回で見てきたように，これらのデータ構築子は直接Haskellのソースコード上に記述できます（Lispをご存じの方なら，[]がnilを(:)がconsを意味することがわかると思います）。このように，Listのデータ型の定義の中には，直接触れることのできないものは存在しません。

　このことは一見，当たり前のように思えますが，そうではありません。前々回に少しだけ触れたモジュールを使えば，データ型の定義を外に公開しないようにできます。そうすると外側からは直接データ構成子やそのデータに含まれる要素には触れることはできず，外側に公開されているインタフェースを使って間接的に触れることしかできません。いわゆる「抽象データ型（ADT: Abstract Data Type）」になるのです。

　抽象データ型の例としては，前回紹介したIOや前々回紹介したByteStringなどが挙げられます。抽象データ型の場合，内部で使用しているデータをすべて取得できるようにする必要は全くありません。そのデータを使うユーザーにこの部分を見せる，と決めた部分だけを公開すれば十分です。このとき外部に公開されている関数を使って取得できるデータが「取り出し可能な値」，外部に公開されている関数からは取得できない，いわゆるブラックボックスになっている部分が「取り出し不可能な値」になります。一方，抽象データ型になっていない場合は，データ型の内部のすべての部分が公開されているため，ユーザーが自由に扱えます。これが「取り出し可能な値」しか持たないということです。

　次にListにおけるmapの定義を見てみましょう。「Haskell 98 言語とライブラリ改訂レポート」では，mapは以下のように定義されています（参考リンク，なお「Haskell 98 言語とライブラリ改訂レポート」での定義は，実装の参考になるよう関数の意味を示したものであることに注意してください。効率よりも関数の意味が明確になることを意識して定義されているため，実際に処理系のライブラリとして実装されているものとは異なることがあります）。

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

　mapの関数を定義している等式が，データ構成子が[]である場合と(:)である場合の二つ存在しているのがわかりますね。この場合分けを行っているのが「パターン照合（pattern matching，パターンマッチ）」と呼ばれる機能です。このように，文字列だけではなく，データ構成子などのより広い範囲のデータ型の構成要素を対象としている点が，正規表現のパターン照合とは違います。また型やPrologなどの論理型言語の「単一化（unification）」とは異なり，「左側のパターン照合によって値に束縛した変数が右側で使用される」という一方通行になっている点にも注意してください。

　さて，mapの定義の意味は以下の通りです。

第二引数が[]，つまり中身が空のリスト（空リスト）であればそのまま空リストを返す
そうでない場合には，先頭の値にfを適用し，後ろのリストにはそのままmap fを適用し，その結果をリストにまとめて返す

　つまり「再帰関数（recursive function）」になっているのです。再帰型，再帰関数と立て続けに再帰が二つ出てきました。再帰は関数型言語にとって欠かすことのできない基本的な概念です。これまで再帰についてほとんど触れずに済んだのは，mapや初回に紹介したiterateなどが高階関数になることで，内部で行われている再帰を覆い隠していたからです。このように繰り返し使われる処理をうまく高階関数にすることで，煩雑な処理をプログラム中に記述することから解放されます。よく使われる処理は，たいていPreludeをはじめとするライブラリに収録されています。自分が書いた処理をリファクタリングできないかなと思ったときにはライブラリのドキュメントやHoogleという検索サイトで探ってみるとよいでしょう。

　再帰や変数の束縛（再代入がないこと）に関する話は，同じくITproで連載されている住井英二郎さんの「数理科学的バグ撲滅方法論のすすめ」の「第2回　「単一代入」と「末尾再帰」」にも書かれているので，詳しくはそちらを参照してください。例示されているコードはHaskellではありませんが，基本になっている部分は同じなので参考になると思います。

Listモナド

　Listやmapに対する説明を終えたところで，ついにListモナドについて見ていくことにしましょう。ListのMonadクラスのインスタンスは，「Haskell 98 言語とライブラリ改訂レポート」では以下のように定義されています（参考リンク）。

instance  Monad []  where
    m >>= k          = concat (map k m)
    return x         = [x]
    fail s           = []

　>>=の定義に使われているconcatは，リストの内部にあるリストを連結し，一つの大きなリストに変える関数です。

Prelude> :i concat
concat :: [[a]] -> [a]  -- Defined in GHC.List
Prelude> concat [[3],[],[1,4]]
[3,1,4]

　concatが[[a]] -> [a]という型を持つことや>>=の定義から，concatが前回説明したjoinに当たるのがわかると思います。

　さて，ある値を取りリストを返す関数(a -> [b])を，mapを使ってリストに適用すると，その結果は[[b]]になります。こうして発生した[[b]]の中身をconcatを使って連結するという操作は，実は関数型言語ではよく使われます。このため，PreludeにはconcatMapという関数も用意されています。定義は「concatMap f = concat . map f」です。concatMapの型が(a -> [b]) -> [a] -> [b]であるのに対し，Listにおける>>=の型は[a] -> (a -> [b]) -> [b]で，引数の順番が逆になっていることに注意してください。

　Listにおける>>=がconcatMapとほぼ同じものだとわかれば，Listをわざわざモナドにする必要はあまりないのではないか，という疑問が出てくるかもしれません。Listをモナドにする意義は一体どこにあるのでしょうか？

　前回の説明を思い出してください。モナドで使用するコンテナは計算を表現し，>>=はその計算を合成してより大きな計算を作り出すという役割を持っているのでした。Listモナドも同様にこれらの条件を満たす計算を行えるのであれば，「単にconcatMapを使うよりもプログラムの意図を明確にできる」という点で，Listをモナドにする意義があるといえます。

　List型はただのリストにしか見えないのに，それ自身が計算であると言われてもすんなり納得はできないかもしれません。そこでまず，リストというコンテナの中に入っているそれぞれの値が「計算の結果」である，ということから順に考えていくことにしましょう。

　ある値に対する計算の答えをリストに収めて返したい，つまり(a -> [b])のような関数を計算にしたいのはどういう場合でしょうか？その一つとして「ある計算によってとり得るすべての答えを表したいとき」が挙げられます。初回に紹介したrepeatedは，まずiterateを使って無限の長さを答えを生成し，その答えの中から望む一個の答えを取り出す関数として定義されていました。また，以下に示すエラトステネスのふるいを使った素数生成の素朴な（naive）実装は，「数列を作り出していくプログラムが無限の答えを持つ」ものになっています。

primes = sieve [2..]
sieve (p:ps) = p : sieve [q | q <- ps, q `mod` p /= 0]

　primesはsieveに2から始まる等差数列を与えることを示しています。..は省略記号です。この場合，初期値である2以外に条件はないので，数値を一つずつ列挙していく方法に従って（つまり1ずつ増加して）数値が生成され，sieveに渡されていきます。ちなみに..の終端や数値の増分は型に依存します。Int型は固定倍長整数であり，少なくとも[-2^29, 2^29 - 1] の範囲をカバーすることになっています（参考リンク）。

　遅延評価を行うので，primesがsieveに渡すリストは今まさに生成している最中のものであっても構いません。sieveは渡されたリストをパターン照合し，最初の要素にp，残りのリストにpsという変数を束縛しています。sieveの定義内で使われている[q | q <- ps, q `mod` p /= 0]という形式は，「リストの内包表記（list comprehension）」と呼ばれるものです。sieveに与えられるリストを生成するにあたって，「リストを構成する値qは，リストpsの値のうち(,)以降に続く条件を満たすものでなければならない」ということを示しています。modは余りを求める関数なので，ここではpで割り切れるものが除外されることになります。なお，<-を使って示している「集合の元となる値や要素を制限する条件式」は複数あっても構いません。リストの内包表記自体をネストすることもできます。

　上記のprimesをPrimes.hsに定義して，primesを評価してみましょう。そのまま評価すると，sieveでは終端を指定していないため素数の列挙がずっと続くことになります。適当なところでCtrl-Cを押して，評価を中断してください。

*Main> :t primes
primes :: [Integer]
*Main> primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
～ 略 ～
,10193,10211,10223,10243,10247Interrupted.

　さて，可能なすべての答えというと複数の答えを返す場合を考えがちですが，逆に答えが全くない場合も考えられます。これは「空リスト（empty list）」を返すことで扱えます。つまり，0個の答えを返しているわけです。答えが0個であるということは，エラー・チェックのように0個を期待するような特別な場合を除き，「計算に失敗している」ととらえるのが普通でしょう。

　このようなリストの特徴を利用して，Listモナドでは，Monadクラスの関数（メソッド（method））であるfailも空リストとして定義されています。failはdo記法内部でパターン照合が失敗したときなどに呼ばれる関数です。要するに，通常はエラーが発生するような場合であっても，Listモナド上ではリストに対する計算の失敗と同様に扱うことを許しているのです（そのように扱われたくないエラーを表現する場合には，別途用意されているerror :: String -> aなどを使うことができます）。