top page > computer > haskell > web_lecture > for_programmer > list_monad.html
更新日:
文責: 重城良国

リストモナド

(工事中 60%)

はじめに

リストもモナドだ。リストがモナドであるということは

g :: a -> [b]
h :: b -> [c]

のふたつの関数をつないでa -> [c]型の関数が作れるということだ。すなおなつなぎかたは以下のようになるだろう。関数gにa型の値をあたえて得られたb型の値のリストのすべての要素に対して関数hを適用して得られたc型の値のリストのリストを一段階のリストに平坦化する。

(g `pipe` h) x = concat $ map h (g x)

リストモナドは可能性のある値すべてを試す演算と考えることができる。

インスタンス宣言

リストははじめから型クラスMonadのインスタンスである。インスタンス宣言は

instance Monad [] where
return = (: [])
m >>= f = concat $ map f m

となる。

平方根の例

list_monad.hs

xの平方根とは2乗するとxになる値のことである。たとえば2乗して4になる値は-2と2だ。4の平方根は-2と2ということになる。2乗して0になる値は0だけだ。また2乗して負になる値は(実数の範囲では)存在しない。あたえられた実数値の平方根となる実数を返す関数は

root :: Double -> [Double]
root 0 = 0
root x
| x < 0 = []
| otherwise = [- sqrt x, sqrt x]

のようになる。これを使ってある値aの平方根に値bを加算した値の平方根(root (root a + b))を求める関数を作成する。

calc :: Double -> Double -> [Double]
calc a b = root a >>= root . (+ b)

試してみる。

% ghci list_monad.hs
*Main> calc 16 5
[-1.0,1.0,-3.0,3.0]
*Main> calc 49 2
[-3.0,3.0]
*Main> calc 1 1
[0.0,-1.4142135623730951,1.4142135623730951]

16の平方根は-4と4でありそれぞれに5を足すと1と9になる。これらの平方根をとると-1, 1, -3, 3となる。49の平方根は-7と7でありそれぞれに2を足すと-5と9になる。-5の実数の平方根は存在しない。9の平方根は3である。1の平方根は-1と1でありそれぞれに1を足すと0と2になる。0の平方根は0であり2の平方根は-1.41421356...と1.41421356...である。

do記法

今回の例であればdo記法を使うのはかえって冗長だ。もっと複雑になるとdo記法によってコードがわかりやすくなることがある。関数calcをdo記法で書くと

calc a b = do
x <- root a
root $ x + b

となる。

条件

たとえば関数calcの結果を非負の値だけにしぼりたいとする。まずは関数grdを定義する。

grd :: Bool -> [()]
grd False = []
grd _ = [()]

これを使って以下のように定義できる。

calc2 :: Double -> Double -> [Double]
calc2 a b = do
x <- root a
y <- root $ x + b
grd $ y >= 0
return y

grd (y >= 0)は何をやっているのだろうか。yが0より小だったときに空リストを返すことでその枝をかりとっている。以下の式を考えてみよう。

[3, 4, 5] >>= const []

これは3に対して[]、4に対して[]、5に対して[]ということだ。[]とは可能性がないということであり、全体としても[]となる。つまり[]によって枝をかりとることが可能ということだ。

メモ

本来ならば

guard :: MonadPlus m => Bool -> m ()

を使うべきだが、MonadPlusの説明がめんどくさいので今回は車輪を再発明して

grd :: Bool -> [()]

を定義して使うことにしよう。

リスト内包表記との関係

リスト内包表記による表現とリストモナドとしての表現はまるで別のことをしているかのように見える。リスト内包表記は「すべての組み合わせにおける演算」でありリストモナドの意味あいは「すべての可能性に対する演算」である。実質的には同じものだ。リスト内包表記は以下のようにリストモナドの書きかたに直せる。

[ expR | var0 <- exp0, var1 <- exp1, ..., varN <- expN ]
|
V
do
var0 <- exp0
var1 <- exp1
.
.
.
varN <- expN
return expR

途中に条件式expBがある場合にはgrd expBのような置きかえをすればいい。calc2をリスト内包表記で書きなおすと

calc2 a b = [ y | x <- root a, y <- root $ x + b, y >= 0 ]

となる。

まとめ

リストモナドは「すべての可能性を追いかける」演算と考えられる。「すべての組み合わせを試す」リスト内包表記と実質的に同じ演算になる。リストモナドとリスト内包表記とは機械的な書きかえが可能だ。

「構文: do記法」へもどる 「拡張機能: MonadComprehensions」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics