概要

Haskell におけるモナドを導入し、リストが非決定性計算を与えることを見る。プログラミングにはある程度親しんでいるものの関数型言語の概念を知らない人を出発点に想定し、なるだけ跳躍のない導入を試みる。同様のトピックを解説した記事は数多存在しており、アプローチが重複していないかの確認はしていない。

導入

Python を例として次のようなコードを考えてみる。関数を順次適用していくことで処理を進めるありきたりのコードである。

a = m
b = f(a)
g(b)

ここで簡単のため f も g も整数を引数／戻り値とする関数であるとしよう。例えば次のように置こう。

def f(a):
    return 2*a
def g(b):
    return b+1

toolz.pipe を用いると上述のコードは次のように書ける。

toolz.pipe(
    m,
    lambda a: f(a),
    lambda b: g(b)
)

ここで toolz.pipe は toolz.pipe(x,f,g,h,...) = ...h(g(f(x))) のように振る舞う関数である。またlambda a:f(a) はaを引数、f(a)を戻り値とする関数を表す。つまり f のことである。

ここから「変数 a に値 m を代入する」という処理は、「引数に記号 a を割り当てた関数を値 m に適用する」こと、に置き換えられることがわかる。これを「代入と関数適用のイメージ」と呼ぶことにする。

上のコードはもちろん次と同じである。

toolz.pipe(m,f,g)

ここで >>= なる記号を導入して上コードを

( m >>= f ) >>= g

と書くことにしてみる。m >>= f は「mをfに渡すこと」すなわちf(m)を意味している。コード全体は「mをfに渡し、その結果をgに渡す」という意味になる。単純な書き換えであるが、「値を関数に渡す」ことが記号化され明示されている。toolz.pipeを用いたコードは値と関数を列挙しただけでこの点は明示的でない。

このコードはさらに

m >>= (\a -> (f a >>= g))

と書き換えてもよい。ここで\a -> f a はPython の lambda a:f(a) と同じ。この書き方は m がたどる運命を1つの関数にまとめている。すなわち「引数をfに渡し、その結果をgに渡す」関数\a -> (f a >>= g)に m を渡している。もう少しねちっこくかけば

m >>= (\a -> (f a >>= (\b -> g b)))

である。g を \b -> g bとしただけである。

ここで「代入と関数適用のイメージ」を逆にたどろう。引数を記号aで表した関数に値mを渡すことは、値mを記号aで表すことと同様なのであった。そのことを a <- mと表すことにすると、これは

do
  a <- m
  b <- f a
  g b

と書いても差し支えない。この記法はdo記法と呼ばれるのでdoを付している。書き換え後、より下段に書かれた式は、書き換え前、より内側の括弧に位置していたこと、また初めのPythonコードと類似しつつそこにあった変数という概念が消失していることに注意されたい。なおこれはほんの少し疑似コードであり Haskell として実行はできない。

以上の流れを振り返ろう。ここでは

関数の戻り値を変数に代入しながら、関数を順次適用していくことでコードを書く
toolz.pipeを用い、変数を使わず関数だけでコードを書く
「値aを関数fに渡す」ことを意味する a >>= fなる記号を導入する
f を \a -> f a として引数記号を明示する
「代入と関数適用のイメージ」に従って式を書き直す。すなわち値を記号に割り当てながら、関数を順次適用していくコードにする

ことを行った。ここで本質的に新しい概念は生まれていない。

非決定性計算

さきほどPythonで記した関数定義をHaskell で書き直しておこう。

f:: Int -> Int
f a = 2*a
g:: Int -> Int
g b = b+1

前節で扱った計算は決定性計算すなわち

のような計算である。ここで非決定性計算すなわち

のような計算を考えたい。たとえば次のような関数を考えよう。

f:: Int -> [Int]
f a = [1*a, 2*a, 3*a]
g:: Int -> [Int]
g b = [b+0, b+1]

図で示した計算の結果を得るだけなら、elephantに繰り返し処理を行えばよい。しかしelegentに記述する方法はないだろうか。関数を順次適用していくという、その有様を？

記号m >>= fを思い出そう。そしてこいつを

m >>= f   ===   concat (map f m)

で定義し直してやろう。いま式の等価性を言うのに===で表すことにした。

ここで map f m は m=[m1,m2,m3,..]のとき[f m1, f m2, f m3, ...] を、cancat は [[a1,b1,...],[a2,b2,...],...] のような入れ子を[a1,b1,...,a2,b2,...]と「なめす」（フラット化する）関数である。対話的環境での実行例は次の通り。

Prelude> f a = [1*a,2*a,3*a]
Prelude> f 2
[2,4,6]
Prelude> map f [1,2,3]
[[1,2,3],[2,4,6],[3,6,9]]
Prelude> concat (map f [1,2,3])
[1,2,3,2,4,6,3,6,9]

すると上の図で示した非決定性計算は前節と同じ次のコードで書けてしまう。

( m >>= f ) >>= g

もちろん関数f,gおよび記号>>=の定義が変わっている。do記法を用いれば、やはり同じコード

do
  a <- m
  b <- f a
  g b

である。この芸当は一番始めに示したPythonのやり方では実現できない。「値を関数に渡す」ことが記号化／明示されていないからである。

例で示したように、m は m=[m1,m2,m3,..] のような [Int]型の変数であることが想定されている。つまりm >>= fを concat (map f m) で定義したので、f(1) を表すのに 1 >>= fのようには、すなわち

do
  a <- 1 -- これはNG
  b <- f a
  g b

のようには書けない。そこで

return:: Int -> [Int]
return x = [x]

という関数を定義しておけば、

do
  a <- return 1 -- これはOK。[1]と同じ。
  b <- f a
  g b

とできる。このreturnは

(return m0) >>= f   ===   f m0
m >>= return   ===   m

という性質を持っている。

モナド

リストモナド

これまでに出て来た登場人物を整理すると、[Int]の構造を鑑みて concat (map f m) で定義された>>=と、便宜的に導入されたreturnが挙げられる。そしてこれらは次の性質を満たしていた。

(m >>= f) >>= g   ===   m >>= (\a -> (f a >>= g))
(return m0) >>= f   ===   f m0
m >>= return   ===   m

この三つ組 ([], >>=, return)をリストモナドと呼ぶ。リストモナドはdo記法の下で非決定性計算をエレガントに表現するモナドであった。

リストモナドを用いた非決定性計算の、もう少し実用的な例を紹介しよう。
$$
H(\mathbf q) = c_0 + c_1 q_2 + c_2 q_3 + c_3 q_4 + c_4 q_2 q_3 + c_5 q_2 q_4 + c_6 q_3 q_4
$$

で示された関数 $H$ が常に $H\geq 0$ かつ、 $q_2q_3=q_4$ かつそのときに限り$H=0$ であるような条件を満たす係数$c_0,c_1,...,c_6$ を求める問題である。ただし$q_i\in\{0, 1\}$ であり $c_i$ は整数であるとする。下のコードは係数の絶対値が小さいものから列挙して5番目までを表示するコードになっている。

import Control.Monad

condition c0 c1 c2 c3 c4 c5 c6 = and $ do
  let z2 = [0,1]
  q2 <- z2
  q3 <- z2
  q4 <- z2
  let h =  c0 + c1*q2 + c2*q3 + c3*q4 + c4*q2*q3 + c5*q2*q4 + c6*q3*q4
  return $ and [h>=0, (q2*q3 == q4)==(h==0)]

coefficients = do
  let z k = 0 : [ y | x<-[1..k], y <- [x,-x]]
  -- z k = {0,1,-1,2,-2,3,..,k,-k}
  let n = [1..]
  k <- n
  c0 <- z k
  c1 <- z k
  c2 <- z k
  c3 <- z k
  c4 <- z k
  c5 <- z k
  c6 <- z k
  guard $ or [c == k | c <- [c0,c1,c2,c3,c4,c5,c6]]
  guard $ condition c0 c1 c2 c3 c4 c5 c6
  return (c0,c1,c2,c3,c4,c5,c6)

main = print $ show $ take 5 coefficients

説明していない記号が含まれているがおおむね意味はお判りになると思う。解法ではなく問題をそのまま記述すれば済むのが非決定性計算のメリットであり、リストモナドがこれを実現している。なおこれは『量子アニーリングの基礎』に掲載されていた問題である。

恒等モナド

始めの節で導いたコードは疑似コードであるといった。これを正確に書くと次のようになる。

import Control.Monad.Identity

f:: Int -> Identity Int
f a = Identity (2*a)
g:: Int -> Identity Int
g b = Identity (b+1)

do
  a <- Identity m
  b <- f a
  g b

Identityはその名の通り恒等、つまり何もしない。ここでは先ほどの [Int] の代わりに Identity Int が検討されている。そこでこれを恒等モナドと呼ぶ。恒等モナドは始めの節で行ったような代入計算の類似を与える。

一般のモナド

[]やidentityを一般化してMと表すことにしよう。このようにして一般のモナドを考えることができる。モナドは

>>=:: M x -> (x -> M y) -> M y
return:: x -> M x

つまりはf::x->M y のようなfとm::M x に対して m >>= f を考えられる記号 >>=
であって

(m >>= f) >>= g   ===   m >>= (\a -> (f a >>= g))
(return m0) >>= f   ===   f m0
m >>= return   ===   m

を満たす三つ組 (M,>>=,return) のことである。

Maybe モナド

最後にありきたりの例であるが、いちおうこの流れでMaybe モナドを紹介する。
まずMaybe は Just a と Nothingの2通りの値を持つ。

data Maybe a = Just a | Nothing

たとえばゼロ除算を考慮する逆数関数は次のように書ける。

inv:: Double -> Maybe Double
inv a
  | a == 0 = Nothing
  | otherwise = Just (1/a)

つまり0 の逆数を計算しようとすると値は Nothing になり、それ以外では Just 1/a とする関数である。
計算が順次適用されるにあたり、ひとたびNothingが出たら結果はNothingであり、そうでなければ Just 1/aから 1/aを取り出して計算を続行する。こうした処理を実装したい。

次のコードは、いま述べた内容そのままである。

Nothing  >>= _  =  Nothing
(Just x) >>= f  =  f x

3つの数を引数にとりその逆数和を計算する関数は次のように書ける。

invsum3 a b c = do
  ai <- inv a
  bi <- inv b
  ci <- inv c
  return $ ai + bi + ci

モナドの性質によって、elephantに引数の0判定をすることなく、elegantに実装できている。結果なしを表すMaybe型に関するこのモナドをMaybeモナド呼ぶ。Maybeモナドは結果なしNothingの伝播や判定をうまく表すことで記述を簡潔にしている。

なおelephant なコードとは次のようなものである。

def inv(a):
  if a == 0:
    return None
  else:
    return 1/a

def invsum3(a,b,c):
  ai = inv(a)
  bi = inv(b)
  ci = inv(c)
  if all([xi is not None for xi in [ai,bi,ci]]):
    return ai + bi + ci
  else:
    return None

こうした関数すべてについていちいち条件分岐を書かねばならないとすると頭の痛くなることである。

まとめ

関数型プログラミングでは関数を順次適用していくことでプログラムを構築する。その順次適用の過程（値を次の関数に渡す）を>>=で明示化してみると、>>=をカスタマイズすることで非決定性計算やゼロ除算による計算失敗の伝播をうまく表すことができる。Intといった基礎的な型に対し、複数の値を取りうることや、値を持たない可能性があることはそれぞれ[Int]，Maybe Intといった型で表される。[]やMaybeは関数の順次適用に特別な処理を要する事情（文脈）を付与しており、こうした事情（文脈）をより一般にMと表すことにすると、Mに応じて定義された>>=にreturnを加えていくつかの基礎的な性質を課したものをモナドと呼ぶ。リストモナドは非決定性計算を表すモナドであり、Maybe モナドは値を持たない可能性を表すモナドであった。