モナド (プログラミング)

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

関数型プログラミングにおいて、モナド(monad)は計算を表現する構造であり、計算ステップの列からなる。つまり、がモナド構造をもつというのは、命令を繋げるやり方、言い換えるとその型をもつ関数をネストさせる規則が定まっていることをいう。これはプログラマがパイプラインを作ることを可能にする。パイプラインでは入力データを1ステップずつ処理するが、モナドは各アクションに追加の処理規則を上乗せすることができる[1]。このことから、モナドは「プログラム可能なセミコロン」と記述することもできる[1]。セミコロンは多くの命令型プログラミング言語で個々のを繋ぐ演算子であり、この例えは、パイプライン中の文の間に追加でコードを実行できることを示唆している。さらにモナドは組み立てラインというメタファーで説明することもできる。ベルトコンベアが機能ユニットの間のデータ転送を行い、各ユニットが一度にひとつずつそれを処理するのである[2]。他にも、ジェネリック型を構築するための関数型デザインパターンと見ることもできる[3]

純粋関数型プログラムでは構造化プログラミングに見られるような、逐次実行する命令列を含む手続きの構成にモナドを利用することができる[4][5]。モナド構造によって、プログラミングにおける多くの共通概念を記述することが可能である。これには入出力といった副作用、変数への代入例外処理構文解析非決定計算並行計算継続がある。言語の意味を大きく拡張することなく、純粋性を保ったままこれらの概念が利用できるようになる。Haskellのような言語ではモナドを標準ライブラリで提供しており、プログラマはこれらの抽象的な定義を再利用することで、多くの異なったライブラリにおいても同じやりかたで機能を合成することが可能になっている[6]

形式的には、モナドは型構築子 M とふたつの演算 bindreturn から構成される(returnunitと呼ぶこともある)。

  • return 演算は素な型の値を受け取って、構築子によりモナド的なコンテナに詰めて返す。これは モナド的な値を作成する。
  • bind 演算はモナド的な値と、素な型の値からモナド的な値への関数を受け取って、新しいモナド的な値を返す。

この演算はモナド的な関数(引数や返り値がモナドである関数)を正しく合成できるように、いくつかの性質を満たさなければならない。プログラムの中に命令を追加するという意味で、モナドはアスペクト指向プログラミングとしての側面もある[7]domain logicはアプリケーションプログラマが定めるのに対して、必要なブックキーピングは前もってモナドとして定義することができる。

名称と概念は圏論にちなむもので、モナドは一種の函手であり、圏の間の写像である。しかし、関数型プログラミングの文脈におけるモナドは通常は圏論における強モナドを指すことが多い[8]

歴史[編集]

プログラミングにおけるモナドの概念は1980年代のプログラム言語Opalに見られるが、このときは「コマンド」と呼ばれ形式化はされなかった[要出典]

1991年にEugenio Moggiはプログラムの構造化でモナドを初めて汎用的に使用した[8]。この成果を元に、Philip WadlerSimon Peyton Jonesといったプログラム言語の研究者(二人ともHaskellの言語仕様に取り組んでいた)により実装が行われた。初期のバージョンのHaskellは問題の多い「遅延リスト」を用いた入出力を使っていたが、Haskell 1.3からは遅延評価により柔軟に合成可能なモナドによる入出力が導入された。

入出力に加えて、プログラム言語研究者とHaskellのライブラリ設計者は構文解析器やインタープリタにモナドを適用することに成功した。Haskellのdo記法に現れる性質から、モナドの概念はapplicative functorarrowへと一般化された。

長い間、Haskellとその派生だけがプログラミングにおけるモナドの主な利用者であった。しかし、SchemePerlPythonRacketClojureScalaにおいても定式化されており、新しいMLの標準でもオプションとなっている。最近では、F#コンピュテーション式または「ワークフロー」と呼ばれる機能を導入した。これは、命令型プログラムしか経験のないプログラマにもなじみやすい構文を使ったモナド的構成を提供しようという試みである[9]

動機付けと例[編集]

プログラム言語Haskellはモナドを多用する関数型の言語であり、簡単にモナドの合成ができるような構文糖衣を持っている。特に指定がない限り、この記事のコード例はHaskellで書かれている。

モナドの紹介として一般的なふたつの例 Maybe モナドと I/O モナドを取り上げる。もちろん、モナドはHaskellに限られたものではないので、JavaScriptでの Writer モナドの例もその次に扱う。

Maybeモナド[編集]

オプション型 Maybe a を考えよう。これは型 a の値をひとつ持つか、全く持たないかのふたつの状態を表現する型である。これらを区別するために、二種類の代数的データ型構成子を持つ。Just tはひとつの値tを保持し、Nothingは値を何も保持しない。

data Maybe t = Just t | Nothing

この型を使って検査例外の簡単なものを作ってみたいとする。計算の途中で失敗した場合は、残りの計算は飛ばして結果Nothingを返し、すべての計算が成功した場合は何か値xを保持したJust xを返すことにする。

以下の例では、addMaybe Int型のふたつの引数を受け取って、同じ型の結果を返す。mxmyがともにJustである場合は、これらの値の和をJustに入れて返したい。もし、mxmyのどちらかがNoneだった場合は、Nothingを返したい。こういった振る舞いをする関数を単純に実装しようとしたら、「if Nothing then Nothing else Just xxに何かする」の形の場合わけを複数ネストすることになり、すぐやっかいなものになる[1]

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =
  case mx of
    Nothing -> Nothing
    Just x  -> case my of
                 Nothing -> Nothing
                 Just y  -> Just (x + y)

これを楽にするための、各計算を繋げる演算子を定義することができる。二項演算子 bind (>>=) は失敗する可能性のある計算の結果を、もうひとつの失敗する可能性のある計算へ連鎖する。最初の引数が Nothing だった場合は、二番目の引数(関数引数)は無視されて、単に計算全体が失敗する。もし、最初の引数が Just x だった場合は、この値 x は二番目の関数引数に渡されて、この関数の結果として新しい Maybe の値が返される。これは Just な値か失敗かのどちらかになる。

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing  >>= _  =  Nothing    -- 失敗した計算は Nothing を返す
(Just x) >>= f  =  f x        -- 値 x に関数 f を適用する

計算の状態に影響を与えずに値を投入する構築子は、Just がすでにそうなっている。

return :: a -> Maybe a
return x = Just x       -- 値 x を包んで、型 (Maybe a) の値として返す

これらを使うことで、上の例は次のように書ける。

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =             -- (Maybe Int) 型のふたつの値を足す関数。各入力は Nothing の場合がある
  mx >>= (\x ->         -- mx が Nothing でない場合に、値 x を抽出する
    my >>= (\y ->       -- my が Nothing でない場合に、値 y を抽出する
      return (x + y)))  -- 値(x+y)を包んで、(Maybe Int)型の値として和を返す

さらにdo記法という構文糖衣を使うことで、次のように書くことができる。

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my = do
  x <- mx
  y <- my
  return (x + y)

この種の操作は頻出なので、Haskellの標準関数(liftM2)が用意されている。これはふたつのモナド的な値(ここでは、ふたつのMaybe)と、その中身(ふたつの数値)を組み合わせる関数(加算)を受け取る関数であり、上の例は次のように書ける。

add :: Maybe Int -> Maybe Int -> Maybe Int
add = liftM2 (+)

(上記のdo記法を使ってliftM2の定義を書いてみよう)

I/Oモナド[編集]

Haskellのような純粋関数型言語では関数が外部から観測可能な作用をもつことは、関数の意味から外れることになるため許されない。しかし、関数が直接副作用を起こすのではなく、求める副作用を記述する値を構築して返し、呼び出した側が適当な時に実行することは可能である[10]。Haskellの記法では、型 IO a の値がこのようなアクションを表現していて、実行されたときには、型 a の何らかの値を生成する。

IO型の値は「現在の世界の状態を引数に取り、関数の返り値として変化した状態を持つ新しい世界を返す」という意味でアクションとみなすことができる。例えば、関数 doesFileExistremoveFile は次の型を持つ関数である。

doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()

removeFile は関数としては、FilePath を引数にとり、ある IOアクションを返す。このアクションが実行されると世界を、この場合はファイルシステムを FilePath という名前のファイルの存在しないものに変更する。この場合は、IO の持っている値は () 型の値なので、なにも結果は生成されず、呼び出し側はこれを気にする必要はない。一方で、doesFileExist の場合は、関数の返す IOアクションはブール型の値、True または Falseを包んでいて、概念的には、アクションが実行されたときのファイルシステムに FilePath という名前のファイルが存在したかどうかを呼び出し側が知っているという世界の状態を表現している。アクションからアクションへと世界の状態を渡して管理するこの方法により、決まった順序で状態を変化させていくアクションの列を定めることが可能となる。この過程は時相論理において宣言的な命題のみで時間の経過を表現する手法と似ている。以下の例ではプログラム内のアクションを連鎖する方法の詳細を再び Haskell を使って明らかにする。

基本的な種類の入出力操作、標準出力に文字列を書く、標準入力から文字列を読む、ファイルの読み書き、ネットワーク越しのデータ送信等をすべて記述できるようにしたい。さらに、これらのプリミティブを組み合わせて大きなプログラムを作れる必要もある。例えば次のように書けることが望ましい。

main :: IO ()
main = do
  putStrLn "What is your name?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

この直観的な記法はどのように形式化できるだろうか?このためには各入出力アクションに対して、いくつかの基本的な操作を実行できる必要がある。

  • ふたつの入出力アクションをひとつにできなければならない。Haskellでは、中置演算子 >> を用いて、putStrLn "abc" >> putStrLn "def" と書き、コンソールに二行の文字列を表示するひとつのアクションである。演算子 >> の型は IO a → IO b → IO b であり、ふたつの入出力アクションを引数に取り、順番に実行するひとつのアクションにまとめて返す。
  • 何もしないという入出力アクションも必要である。これは値を返すがなんの副作用も持たない。Haskellではこのアクションは return で構築され、この型は a → IO a である。
  • さらに、最初のアクションの結果に基づいて次に実行するアクションを決める必要がある場合がある。Haskellでは、演算子 >>= (bindと読む)を使い、型は IO a → (a → IO b) → IO b である。左側のオペランドは型 a の値を返す入出力アクションであり、右側のオペランドは左側のアクションの生成した値に応じて次に実行する入出力アクションを選択する関数である。結果は、最初のアクションを実行しその値を関数に渡した評価結果をアクションとして実行し、最後にこのアクションの結果を返す合成されたひとつのアクションとなる。
Haskellのこの演算子を使った例は getLine >>= putStrLn であり、これは標準入力から一行文字列を読み込み、それをそのまま標準出力に書き出す。最初の演算子 >> は単にこの演算子の特別な場合である。最初のアクションの結果は無視され、二番目のアクションは常に同じである。

これらの3つの演算子をプリミティブな入出力操作として「いかなるプログラムでも」書けるかというのは、データ変換(ラムダ式使う)やif式やループを含めたとしても自明であるとは言いがたい。上の例は長い式を使って次のように書ける。

main =
  putStrLn "What is your name?" >> 
  getLine >>= \name ->
  putStrLn ("Nice to meet you, " ++ name ++ "!")

bind 演算子の持つパイプライン構造により、getLineputStrLn の命令はそれぞれ一度だけ、書いた順序で評価され、入力ストリームから文字列を取り出して、出力ストリームに出力する副作用は関数型パイプラインの中でも正しく実行される。これは言語が関数をアウト・オブ・オーダー実行遅延評価する場合でも成立する。

明らかに入出力の定義とMaybeの定義は共通の構造を持っているが、異なっている部分も多い。上述した構造や他のよくある似たような多くの構造の抽象化である。モナドの一般化された概念は、計算の一部が副作用を発生させるにも関わらず、純粋関数的な計算として実行したくなるようなあらゆる状況を包含している。

形式的定義[編集]

モナドは、元となる型システムが与えられたとき、その内部に対応する型システム(モナド的型システムと呼ぶ)を埋め込む構成である(つまり、各モナド的型は元のシステムの型でもある)。このモナド的型システムは元の型システムの重要な点は全て保存するが、モナドに固有の特徴を追加する[注釈 1]

プログラミングにおけるモナドの普通の定式化はクライスリトリプルであり、以下の要素からなる。

  1. 型構築子 はそれぞれの元の型から対応するモナド的型を得る方法を定める。Haskellの記法では、モナドの名前は型構築子で表す。M をモナドの名前とし、t をデータ型とすると、M t は対応するモナドの中の型である。
  2. unit 関数 は元の型の値を対応するモナド的型の値にうつす写像である。unit 関数は多相的な型 t→M t を持つ。通常、結果は対応する型の値の中でもっとも単純なものであり、元の値を完全に保存している(単にモナドに合わせて、適当に解釈するだけである)。Haskellにおいては、この関数は return と呼ばれる。この名前は後述する do 記法での使われ方から来ている。
  3. bind 演算子 は多相的な型 (M t)→(t→M u)→(M u) を持ち、Haskellでは中置演算子 >>= で表現する。最初の引数はモナド的な型の値であり、二番目の引数は最初の引数の元になった型の値を受け取って、他のモナド的な型の値を結果として返す関数である。典型的には、次の4段階で理解される。
    1. 最初の引数のモナドに関連した構造に「穴を開け」て、元になった型のいくつかの値を露出させる。
    2. これらの各々の値に与えられた関数を適用して型 (M u) の値をいくつか得る。
    3. 再び、この結果のモナドに関連した構造に穴を開けて、型 u の値をいくつか露出させる。
    4. 最後に、すべての結果を元にモナドに関連した構造を再構築し、型 (M u) の値を得る。

型構築子 M が与えられたとき、ほとんどの文脈では、型 M a の値は型 a を返すアクションだと考えることができる。return 演算子は素の型 a の値を受け取り、モナド的なコンテナ型 M a に入れる。bind 演算子は型 M a のモナド的な値と型 a → M b を持つ関数を連鎖させて、型 M b のモナド的な値を作成する。

モナド則[編集]

モナドが正しく振舞うためには、いくつかのモナド則と呼ばれる公理にしたがって定義されていなければならない[11]。 以下、記号 ≡ はHaskellの式が等価であることを示す。

  • return>>= に対して、ほとんど単位元である。
    • (return x) >>= f f x
    • m >>= return m
  • ふたつの関数を続けて bind するのは、これらの関数から決まるひとつの関数を bind することに等しい。
    • (m >>= f) >>= g m >>= ( \x -> (f x >>= g) )

公理を do 記法で表現することもできる。

  • do { f x } do { v <- return x; f v }
  • do { m } do { v <- m; return v }
  • do { x <- m; y <- f x; g y } do { y <- do { x <- m; f x }; g y }

また、モナド合成演算子 (f >=> g) x = (f x) >>= g を使うと

  • return >=> g g
  • f >=> return f
  • (f >=> g) >=> h f >=> (g >=> h)

fmap と join[編集]

Haskellではモナドを returnbind 関数を用いて定義するが、return にふたつの演算子 joinfmap を加えることでも定義可能である。この定式化は圏論における元のモナドの定義により近くなる。fmap 演算子は型 (tu) → M t→M u[12] を持ち、ふたつの型間の関数を受け取って、モナドの中の値に「同じこと」をする関数を返す。join 演算子は型 M (M t)→M t を持ち、二層になったモナド的な情報を平らにしてひとつにする。

ふたつの定式化は以下の関係を持つ。

fmap f m = m >>= (return . f)
join n = n >>= id

m >>= g      join (fmap g m)

ここで、m は M t、n は M (M r)、f は tu、g は t → M v の型を持つ。truv は元の型である。

モナドでなくても、型と関数からなる圏では fmap 関数は任意の函手に対して定義できる。函手は次の法則を満たす。

fmap id      id
fmap (f . g)      (fmap f) . (fmap g)

同じ圏で、return基点付き函手英語版を特徴付ける。これは値を函手の中に「持ち上げる」ことによる。満たすべき法則は次の通りである。

return . f  fmap f . return

さらに、join によってモナドが特徴付けられる。

join . fmap join      join . join
join . fmap return    join . return = id
join . fmap (fmap f)  fmap f . join

加法的モナド[編集]

加法的モナドは、モノイド則を満たす二項演算子 mplusとその単位元としてモナド的な値 mzero を備えたモナドである。演算子 mplus の型は M tM tM t であり(ここで、M はモナドの構築子であり t は元の型である)、結合律と左右からの単位元律を満たす。

(a `mplus` b) `mplus` c   =   a `mplus` (b `mplus` c)
m `mplus` mzero              mzero `mplus` m               m

このことから、加法的モナドはモノイドでもある。>>=に対しては、mzeroはヌル要素として振舞う。ゼロを掛けるとゼロになるように、mzero と関数を bind すると結果はゼロとなる。

mzero >>= f                  mzero

同様に、モナド的な値 m とつねにゼロを返す関数を bind すると、結果はゼロである。

m >>= (\x -> mzero)          mzero

直観的には、モナド的値としてのゼロはモナドに関連した構造だけを持ち元の型の値を持たない。Maybe モナドでは、「Nothing」がゼロである。リストモナドでは、空リストがゼロである。

構文糖衣: do記法[編集]

bind 演算子 >>= を直接使ってプログラムを書くのがよい場合もあるが、典型的にはdo記法 (OCamlでは perform記法、F#ではコンピュテーション式)を使用し、命令型言語のような見た目にできる。コンパイラはdo記法の式を >>= を使ったものに変換する。例えば

a = do x <- [3..4]
       [1..2]
       return (x, 42)

を変換した結果は以下となる。

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))

リストモナドの実装を見てみよう。リストにマップを行い結合を行う(平らにする)この関数は concatMap とも呼ばれる。

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

よって、以下のような変形が行われて、それぞれの式はすべて等価である。

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))
a = [3..4] >>= (\x -> concatMap (\_ -> return (x, 42)) [1..2] )
a = [3..4] >>= (\x -> [(x,42),(x,42)] )
a = concatMap (\x -> [(x,42),(x,42)] ) [3..4]
a = [(3,42),(3,42),(4,42),(4,42)]

リスト[1..2]は使われないことに注意しよう。左矢印をつけないことで、連鎖した関数は引数を無視するように変換されて、値ではなくモナド的な構造だけが問題になることを示すことができる。例えば、状態モナドで値を生成せずに状態だけを変化させるようなときに使われる。do記法は >>= の単なる構文糖衣であるので、どんなモナドに対しても使うことができる。

Maybeモナドの値を安全に割り算する以下の定義も等価である。

x // y = do
  a <- x  -- xとyの中に値がある場合は取り出す
  b <- y
  if b == 0 then Nothing else Just (a / b)

x // y = x >>= (\a -> y >>= (\b -> if b == 0 then Nothing else Just (a / b)))

同様にF#ではコンピュテーション式を使うことができる。

let readNum () =
  let s = Console.ReadLine()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None

let secure_div = 
  maybe { 
    let! x = readNum()
    let! y = readNum()
    if (y = 0) 
    then None
    else return (x / y)
  }

このmaybeブロックは構文糖衣であり、以下の式に変換される。

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return(x / y))))

モナド的な汎用関数[編集]

安全な割り算の結果は、値が Nothing であるかを素直に確認せずに(つまり割り算の結果があるかを確認せずに)そのまま計算に使えたほうが便利なことがある。これは「持ち上げ英語版」関数を使うことで可能である。この関数は Maybe に限定されず、任意のモナドに対して定義される。Haskellでは LiftM2 と呼ばれる。

liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 op mx my = do
    x <- mx
    y <- my
    return (op x y)

関数型を示す矢印が右結合であることから、liftM2は2引数の関数を引数に取って、さらなる2引数の関数を返す。型シグネチャは m がモナドのとき、任意の2引数関数を「持ち上げ」ることができることを示している。例えば、

(.*.) :: (Monad m, Num a) => m a -> m a -> m a
x .*. y = liftM2 (*) x y

は演算子 (.*.) を定義し、それは引数がどちらも Nothing でないときに、掛け算した結果を返す(どちらかが Nothing の場合は Nothing を返す)。この方法の利点はモナドの実装に深入りする必要がないことである。他の同じような関数やモナドを使う場合でも、liftM2 を使うことで、やりたいことが鮮明になる(コードの再利用を見よ)。

数学的には、liftM2 は次のように定義される。

\text{liftM2} \colon \forall M \colon \text{monad}, \; (A_1 \to A_2 \to R) \to M \, A_1 \to M \, A_2 \to M \, R =  op \mapsto m_1 \mapsto m_2 \mapsto \text{bind} \; m_1 \; (a_1 \mapsto \text{bind} \; m_2 \; (a_2 \mapsto \text{return} \; (op \, a_1 \, a_2)))

他の例[編集]

恒等モナド[編集]

もっとも単純なモナドは恒等モナドであり、値になんの情報も付加しない。

Id t = t
return x = x
x >>= f = f x

このモナドのdoブロックは変数の代入を実行する。例えば、do {x <- 2; return (3*x)} の結果は6である。

圏論的な見方をすると、恒等モナドは恒等函手の間の随伴から得られる。

コレクション[編集]

リスト集合多重集合といった、おなじみのコレクション型にもモナドであるものがある。リストの場合の定義は次のようになる。

-- "return" constructs a one-item list.
return x = [x]
-- "bind" concatenates the lists obtained by applying f to each item in list xs.
xs >>= f = concat (map f xs)
-- The zero object is an empty list.
mzero = []

リスト内包記法英語版はリストモナドに固有のもので、例えば、リスト内包 [ 2*x | x <- [1..n], isOkay x] はリストモナドでの計算 do {x <- [1..n]; if isOkay x then return (2*x) else mzero;} に対応している。

リスト内包記法は集合の内包記法に似ていが、集合はモナドにならない。なぜなら、計算の型は等しいかどうかを比較可能でなければならない — モナドは計算の型についてこれを課していないように見えるにも関わらず — という制限があるからである。実際、集合は制限されたモナド(restricted monad)である[13]。コレクションによるモナドは非決定計算を自然に表現する。リスト(または他のコレクション)は非決定的な計算の異なった実行パスが今の時点で取りうる結果の全体を表す。例えば、x <- [1,2,3,4,5] を実行したとすると、変数 x はこのリストから非決定的に選ばれた値であるとみなしている。xを返すことは、各実行パスの結果を値のリストにまとめることを意味する。さらに、bind 演算子では今の可能な結果に対して関数 f を実行し、それぞれの結果をひとつのリストに結合する。

if condition x y then return () else mzeroの形の文はよく現れる。条件が真である場合は何もしない計算を非決定的に選択し、意味のある値は返さない。一方で、条件が偽の場合は、選択肢の存在しない非決定な値 mzero = [] を返す。つまり、この実行パスを終了し、他の実行パスは走り続ける。これは条件を満たす特定の実行パスだけを通す「ガード」の役割を果たす。よって、コレクションモナドは論理パズルや数独などの問題を解く場合に役に立つ。

Haskellのように遅延評価を行う言語では、リストはその要素が必要になって初めて評価される。例えばリストの最初の要素を要求した場合は、最初の要素だけが計算される。非決定計算にリストモナドを使用した場合には、全ての計算からなる結果は非決定的に遅延リストとして生成され、最初の要素を要求すると、必要最小限の計算のみが行われて、最初の結果を返す。この過程はバックトラックに対応している。ある実行パスにいて計算に失敗した(mzeroに評価された)場合、最後に行った分岐までバックトラックを行い、そこから次のパスを選んで実行を続ける。二番目の要素が要求された場合、再びその答を得るのに必要な最小限の計算が行われる。よって、遅延評価の言語ではリストモナドを使って簡単にバックトラックを実装することができる。

圏論的な見方をすると、コレクションモナドは集合の圏とモノイドの圏の間の自由函手英語版忘却函手の随伴から作られる。

コレクションの種類 モノイドの種類
リスト モノイド
有限多重集合 可換モノイド
有限集合 冪等可換モノイド
finite permutation 冪等非可換モノイド

状態モナド[編集]

状態モナドは状態を付加した計算の型である。好きな型に対して、その型を状態として持つ状態モナドを作ることができる。これは状態を引数に取り、通常の返り値(型 t の値)と新しい状態(型 s の値)を返す関数である。

type State s t = s -> (t, s)

今までに見たモナドと違い、状態の型という型引数を取ることに注意しよう。モナドの演算は次のように定義される。

-- "return" は状態を更新せず、受け取った値を生成する
return x = \s -> (x, s)
-- "bind" は m が変更した状態を f に渡して結果とする
m >>= f = \r -> let (x, s) = m r in (f x) s

状態を操作する関数を挙げる。

get = \s -> (s, s) -- 現時点での状態を見る
put s = \_ -> ((), s) -- 状態を上書きする
modify f = \s -> ((), f s) -- 状態を更新する

初期状態を指定して状態モナドを実行する関数。

runState :: State s a -> s -> (a, s)
runState t s = t s

状態モナドのdoブロック内の計算は状態の確認や更新を行うことができる。

非形式的に書くと、状態の型 S を持つ状態モナドは返り値の型 T を関数型 S \rarr T \times S に変換する。return は単に

\text{return} \colon T \rarr S \rarr T \times S = t \mapsto s \mapsto (t, s)

であり、bind

\text{bind} \colon (S \rarr T \times S) \rarr (T \rarr S \rarr T' \times S) \rarr S \rarr T' \times S \ = m \mapsto k \mapsto s \mapsto (k \ t \ s') \quad \text{where} \; (t, s') = m \, s

である。

圏論的な見方では、状態モナドはデカルト閉圏の定義に現れる積函手と指数函手の随伴から作られる。

環境モナド[編集]

環境モナド(Readerモナド関数モナドとも呼ばれる)は環境を共有した計算を可能にする。型構築子は型 T を 関数型 ET にうつす。ここで、E は共有したい環境の型である。モナド演算子は

\text{return} \colon T \rarr E \rarr T = t \mapsto e \mapsto t
\text{bind} \colon (E \rarr T) \rarr (T \rarr E \rarr T') \rarr E \rarr T' = r \mapsto f \mapsto e \mapsto f \, (r \, e) \, e

で定義される。

環境を操作する関数として

\text{ask} \colon E \rarr E = \text{id}_E
\text{local} \colon (E \rarr E) \rarr (E \rarr T) \rarr E \rarr T = f \mapsto c \mapsto e \mapsto c \, (f \, e)

がある。ask は現在の環境を取得するのに使う。localは指定した計算を一時的に変更した環境で行う。状態モナドと同様に、環境モナドによる計算は単に環境の値にモナドの値を適用することで実行できる。

Writerモナド[編集]

Writerモナドは本来の計算を行いながら、様々な種類の追加の出力を作成することができる計算である。ログ取りやプロファイリングに有用である。元の型 T に対して、Writerモナドは型 W × T の値を持つ。ここで、W はモノイド則を満たす演算を持った型である。すなわち、W は二項演算子 (a,b) → a*b と単位元 ε を持っており、これは結合則 (a*b)*c = a*(b*c) を満たし、任意の x について、x*ε = ε*x = x を満たす。

モナド演算は

\text{return} \colon T \rarr W \times T = t \mapsto (\epsilon, t)
\text{bind} \colon (W \times T) \rarr (T \rarr W \times T') \rarr W \times T' = (w, t) \mapsto f \mapsto (w * w',\, t') \quad \text{where} \; (w', t') = f \, t

で定義される。ここで、εと * はモノイド W の単位元と二項演算子である。

JavaScriptではWriterモナドの値として2要素の配列を使うことができる。最初の要素は任意の値であり、二番目の要素は出力を貯めておくための配列である。

var writer = [ value, [] ];

角括弧はこのモナドの値コンストラクタとして使っていて、より単純な要素(配列の0番目は値、1番目にはログ配列)からWriterモナドの値を作っている。

unit (return はJavaScriptの予約語なのでこちらを使う)は元の値に空のログ配列をつけるだけである。

var unit = function(value) { return [ value, [] ]; };

bind は最初のWriterモナドの中の値に関数を適用し、それぞれのログ配列を結合して新しいモナドの値として返す。

var bind = function(writer, transform) {
    var value  = writer[0];
    var log    = writer[1];
    var result = transform(value);
    return [ result[0], log.concat(result[1]) ];
};

pipelineは補助関数で関数の配列を順番に bind する。

var pipeline = function(writer, transforms) {
    var result = writer;
    transforms.forEach(function (transform) {
        result = bind(result, transform);
    });
    return result;
};

モナドの値を返す関数の例を挙げる。

var squared = function(x) {
    return [ x * x, 'was squared.' ];
};

var halved = function(x) {
    return [ x / 2, 'was halved.' ];
};

最後に数学関数のパイプラインにデバッグ情報(デバッグ情報の配列は結合されて、値と一緒に返される)を追加する例を挙げる。

pipeline(unit(4), [ squared, halved ]); // [ 8, [ 'was squared.', 'was halved.' ] ]

継続モナド[編集]

結果の型 R継続モナドは型 T を関数型 \left( T \rarr R \right) \rarr R にうつす。これは継続渡しスタイルのモデルとして使われる。return と bind 関数の定義は

\text{return} \colon T \rarr \left( T \rarr R \right) \rarr R = t \mapsto f \mapsto f \, t
\text{bind} \colon \left( \left( T \rarr R \right) \rarr R \right) \rarr \left( T \rarr \left( T' \rarr R \right) \rarr R \right) \rarr \left( T' \rarr R \right) \rarr R= c \mapsto f \mapsto k \mapsto c \, \left( t \mapsto f \, t \, k \right)

である。

call-with-current-continuation英語版関数は次で定義できる。

\text{call/cc} \colon \left( \left( T \rarr \left( T' \rarr R \right) \rarr R \right) \rarr \left( T \rarr R \right) \rarr R \right) \rarr \left( T \rarr R \right) \rarr R = f \mapsto k \mapsto \left( f \left( t \mapsto x \mapsto k \, t \right) \, k \right)

他の例[編集]

研究者により発見されたモナドになる概念を挙げる。

自由モナド[編集]

自由モナドは自由モノイドと似ていて、直観的には、使う型に依存せずにモナド則(またはモノイド則)を満たすようにできる汎用の構造である。

型 t に対して、t の自由モノイドは [t] であり、結合的な二項演算子として ++、単位元として [] を選ぶ。Haskellでは以下のように書ける。

instance Functor [] where
   fmap _ [] = []
   fmap fun (x:xs) = fun x : fmap fun xs

instance Monoid [t] where
   mappend xs ys = xs ++ ys
   mempty = []

具体的なモノイドとでは、値 t1,t2,...,tn を二項演算で足すことができるが、[] では単に、結合 [t1,t2,...,tn] になるだけであり、単に「一緒に集めた」だけである。ここで、「一緒に集めた」結果がどうなるべきかは定めない。

自由モナドも同じ考えに基づいて定義される。上の定義 List t = Nil | Cons t (List t) に函手を挿入することで、次の定義を得る。

data Free f a = Return a | Bind (f (Free f a))

instance Functor f => Functor (Free f) where
   fmap fun (Return x) = Return (fun x)
   fmap fun (Bind x) = Bind (fmap (fmap fun) x)

instance Functor f => Monad (Free f) where
   return x = Return x
   x >>= fun = Bind (fmap (>>= fun) x)

List が値のリストを保存するのと違って、Free はドメインの値を決めた函手のリストを保存する。FreeFunctorMonad インスタンスの定義によると、受け取った関数を fmap でリストに落としているだけしかしていないことが分かる。

コモナド[編集]

コモナドはモナドの圏論的な双対である。型構築子 W T と2つの演算 extractextend を持つ。extract の型は W TT であり、extend の型は (W TT' ) → W T → W T' であり、以下のコモナド則を満たすとする。

\text{extend} \,\, \text{extract} = \text{id}
\text{extract} \circ (\text{extend} \, f) = f
(\text{extend} \, f) \circ (\text{extend} \, g) = \text{extend} \, (f \circ (\text{extend} \, g))

他の方法として、fmapextractduplicate を使った定義もできる。fmapextract により W は余基点付き函手となる。duplicate がコモナドを特徴付ける。duplicate の型は W T → W (W T) であり、次の規則を満たす。

\text{extract} \circ \text{duplicate} = \text{id}
\text{fmap} \, \text{extract} \circ \text{duplicate} = \text{id}
\text{duplicate} \circ \text{duplicate} = \text{fmap} \, \text{duplicate} \circ \text{duplicate}

ふたつの定式化の関係は

\text{fmap}: (A \rarr B) \rarr \mathrm{W} \, A \rarr \mathrm{W} \, B = f \mapsto \text{extend} \, (f \circ \text{extract})
\text{duplicate}: \mathrm{W} \, A \rarr \mathrm{W} \, \mathrm{W} \, A = \text{extend} \, \text{id}
\text{extend}: (\mathrm{W} \, A \rarr B) \rarr \mathrm{W} \, A \rarr \mathrm{W} \, B = f \mapsto (\text{fmap} \, f) \circ \text{duplicate}

で与えられる。

モナドが副作用を表現すると言われているのに対して、コモナド W は一種の「文脈」を表している。extract は文脈から値を取り出す関数である。extend は型 W AB を持つ「文脈依存の関数」を合成してパイプラインを作る。

恒等コモナド[編集]

恒等コモナドはもっとも単純なコモナドであり、型 T をそれ自身にうつす。extractは恒等関数であり、extendは関数適用である。

積コモナド[編集]

積コモナドは型 T を積の型 C \times T にうつす。ここで C はコモナドの文脈の型である。コモナド演算は

\text{extract}: (C \times T) \rarr T = (c, t) \mapsto t
\text{extend}: ((C \times A) \rarr B) \rarr C \times A \rarr C \times B = f \mapsto (c, a) \mapsto (c, f \, (c, a))
\text{fmap}: (A \rarr B) \rarr (C \times A) \rarr (C \times B) = (c, a) \mapsto (c, f \, a)
\text{duplicate}: (C \times A) \rarr (C \times (C \times A)) = (c, a) \mapsto (c, (c, a))

で定める。

関数コモナド[編集]

関数コモナドは型 T を関数型 M \rarr T にうつす。ここで、M はモノイド構造を持つ型である。コモナド演算は

\text{extract}: (M \rarr T) \rarr T = f \mapsto f \, \varepsilon
\text{extend}: ((M \rarr A) \rarr B) \rarr (M \rarr A) \rarr M \rarr B = f \mapsto g \mapsto m \mapsto f \, (m' \mapsto g \, (m * m'))
\text{fmap}: (A \rarr B) \rarr (M \rarr A) \rarr M \rarr B = f \mapsto g \mapsto (f \circ g)
\text{duplicate}: (M \rarr A) \rarr M \rarr (M \rarr A) = f \mapsto m \mapsto m' \mapsto f \, (m * m')

で定める。εと * はモノイド M の単位元と二項演算子である。

余状態コモナド[編集]

余状態コモナドは型 T を型 (S \rarr T) \times S にうつす。ここで S はストアの型である。コモナド演算は

\text{extract}: ((S \rarr T) \times S) \rarr T = (f, s) \mapsto f \, s
\text{extend}: (((S \rarr A) \times S) \rarr B) \rarr ((S \rarr A) \times S) \rarr (S \rarr B) \times S \,= f \mapsto (g, s) \mapsto ((s' \mapsto f \, (g, s')), s)
\text{fmap}: (A \rarr B) \rarr ((S \rarr A) \times S) \rarr (S \rarr B) \times S = f \mapsto (f', s) \mapsto (f \circ f', s)
\text{duplicate}: ((S \rarr A) \times S) \rarr (S \rarr ((S \rarr A) \times S)) \times S = (f, s) \mapsto ((s' \mapsto (f, s')), s)

で定義される。

関連項目[編集]

脚注[編集]

  1. ^ 技術的には、モナドは元となる型を保存する必要はない。例えば、全ての演算子がただひとつの多相な値を返すような自明なモナドもモナドの公理を満たす。逆に、モナドは新しい構造を追加する必要はない。元の型を変更せずそのままとする恒等モナドはモナドの公理を満たし、モナド変換子の再帰の基点として有用である。

参考文献[編集]

  1. ^ a b c O'Sullivan, Bryan; Goerzen, John; Stewart, Don. Real World Haskell. O'Reilly, 2009. ch. 14.
  2. ^ A physical analogy for monads”. 2010年9月10日時点のオリジナルよりアーカイブ。2015年2月21日閲覧。
  3. ^ Eric Lippert. “Monads, part one”. 2013年9月6日閲覧。
  4. ^ Wadler, Philip. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
  5. ^ Wadler, Philip. The Essence of Functional Programming. Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1992.
  6. ^ Hughes, J. (2005). Programming with arrows. In Advanced Functional Programming (pp. 73-129). Springer Berlin Heidelberg. "
  7. ^ De Meuter, Wolfgang. "Monads as a theoretical foundation for AOP". Workshop on Aspect Oriented Programming, ECOOP 1997.
  8. ^ a b Moggi, Eugenio (1991). "Notions of computation and monads". Information and Computation 93 (1). doi:10.1016/0890-5401(91)90052-4. 
  9. ^ Some Details on F# Computation Expressions”. 2007年12月14日閲覧。
  10. ^ Peyton Jones, Simon L.; Wadler, Philip. Imperative Functional Programming. Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina. 1993
  11. ^ Monad laws”. HaskellWiki. haskell.org. 2011年12月11日閲覧。
  12. ^ Functors, Applicative Functors and Monoids”. learnyouahaskell.com. 2015年2月21日閲覧。
  13. ^ How to make Data.Set a monad shows an implementation of the Set restricted monad in Haskell

外部リンク[編集]

Haskellのモナドチュートリアル[編集]

古いチュートリアル[編集]

他の文書[編集]

Scala のモナドチュートリアル[編集]

他の言語におけるモナド[編集]