コンピュテーション式の練習として、いくつかモナドを作ってみました。BindとReturnだけで何ができるのかをイメージするのが目的です。

モナドやHaskellは前提知識とはしません。モナドを理解していなくても動きを追うことは可能です。最初にHaskellで例を示しますが、すぐ対応するF#を示すので推測できるはずです。

この記事は次の続編です。

doブロックとコンピュテーション式 2016.07.01

今回扱うモナドの詳細は以下を参照してください。

他の言語でも似たようなことをした記事です。

モナド

※ この節の説明は前提知識がないと意味不明だと思います。先に実例に触れて振り返るときの指針として言及しているだけなので、適当に受け流して先に進んでください。

returnと>>=(bind)で操作できてモナド則を満たすものをモナドと呼びます。

モナド則

モナド則はreturnと>>=の動きに関するルールです。

return x >>= f == f x
m >>= return == m
(m >>= f) >>= g == m >>= (\x -> f x >>= g)

いきなり見ても理解できる代物ではないので、あまり気にしなくても構いません。一応、読み方を説明しておきます。

各モナド則は式を == で区切り、左辺と右辺が等しいかを見ます。
等しくなるものがモナドだ、というルールです。
等しくならないものは作れますが、それはモナドではありません。

これで何ができるかは一意に決まるようなものではありません。色々できるとしか言いようがありません。紙と鉛筆で何ができるかと言われて「文章が書ける、計算ができる、絵が描ける」と答えるようなものです。それに相当する具体例として何種類かのモナドを示します。

関数モナド
Stateモナド
リストモナド
Maybeモナド

※ 個々のモナドが何らかの抽象的な原理（モナドの本質？圏論？）から導出されたと捉えない方が良いです。わけがわからなくなります。returnと>>=は紙と鉛筆みたいなもので、その組み合わせでうまくいくものがいくつか発見されている、くらいに考えるのが良いでしょう。

オペランド

>>=のオペランドはモナド則3にも表れているようにm >>= fと書くことが多いです。mはモナド、fは関数を表します。

媒介変数xで表したものと比較してみます。

Haskell

test1 = m >>= f
test2 = do
    x <- m
    f x
test3 = m >>= \x -> f x

test1 と test2 と test3 はすべて同じ動作を表します。

test2 では m から取り出した値を x に束縛して、x を f に引数として渡しています。実態としては x への束縛は関数の引数として表現されており、それを明示したのが test3 です。ラムダ式で受け取った x をそのまま f に取り回しているだけなので f 単体と等価となり test1 に戻ります。

コンピュテーション式

コンピュテーション式はモナドを実装することも考慮されていますが、モナド専用というわけではありません。意図的にモナド則を満たさない「モナドもどき」を作ることは可能で、今回は扱いませんがそれも場合によっては有用かもしれません。

【追記 2016.07.04】モナドもどきを作ってみた例です。

試作したコンピュテーション式と関数モナド 2016.07.04

作業手順

作業手順をパターン化します。

Haskellの例
doを剥がす
returnを実装
1段で>>=を実装
多段対応
ビルダーを実装

関数モナド

渡した引数を補って計算するモナドです。

m >>= fのmの部分に関数が来ます。これは関数をモナドとして扱っているという意味合いで「関数モナド」です。

1. Haskellの例

まずお手本としてHaskellを見ます。

Haskell

test = do
    a <- (+ 1)
    b <- (* 2)
    return (a, b)

main = do
    print (test 3)
    print (test 5)

実行結果

(4,6)
(6,10)

2. doを剥がす

testからdoを剥がします。

Haskell

test =
    (+ 1) >>= \a ->
    (* 2) >>= \b ->
    return (a, b)

ラムダ式のネストが分かりにくいため、括弧とネストを付けたものを示します。

Haskell

test =
    (+ 1) >>= (\a ->
        (* 2) >>= (\b ->
            return (a, b)))

後ろがどんどん深くなっています。ただ、実際に考えるときは最初に示したようなフラットにイメージしておいた方が混乱が少ないです。ラムダ式の範囲を意識する必要があれば変形して確認すれば良いです。

3. returnを実装

渡された引数を無視して指定した値を返す関数を返します。

これをF#で実装します。予約語との衝突を避けるためretとします。

let ret x = fun _ -> x

let test = ret 8

do
    printfn "%A" (test 3)
    printfn "%A" (test 5)

実行結果

8
8

testに渡された引数を無視しています。

let ret x _ = x と書いても動作は同じです（カリー化）。今回は ret の引数は1つで関数を返すという意図を表すため、右辺に fun を明示的に書きました。

4. 1段で>>=を実装

いきなり多段を考えると混乱するので、まずは1段で考えます。

Haskell

test = (+ 1) >>= return

main = do
    print (test 3)
    print (test 5)

実行結果

4
6

m >>= f全体で1引数の関数が構成されます。testに引数を渡して評価できるのはそのためです。

これをF#で実装します。

let ret   x   = fun _ -> x
let (>>=) m f = fun x -> f (m x) ()

let test = (fun x -> x + 1) >>= ret

do
    printfn "%A" (test 3)
    printfn "%A" (test 5)

実行結果

4
6

f (m x)だけではなく、その後で更に()を渡しているのがしっくり来ないかもしれません。

※ ()を渡すことには問題がありますが、今の段階では分からないことなので、後で検証します。

ret をインライン展開して考えます。

let test = (fun x -> x + 1) >>= (fun x -> (fun _ -> x))

>>= で左右に区切って考えます。左辺の fun x -> x + 1 を評価した値が右辺に渡されます。それが引数として x に束縛されて fun _ -> x が返されます。これに () を渡せば x が取り出せます。

>>= の実装と見比べれば、以下のステップで評価が進むことが分かります。

(m x) 左辺を評価
f (m x) 戻り値を右辺に渡して、引数へ束縛
f (m x) () 返された関数を評価

右辺が ret であれば値から関数を返すので、(m x) を渡すだけでは関数が返って来ます。そのため更に引数を渡して関数を評価しているわけです。ret に渡される引数は無視されるので適当に () を渡しています。

f への1番目の引数が値の束縛、2番目の引数が次の式の評価に使われます。

※ モナド則2により let test = fun x -> x + 1 と単純化されます。これはつまり let test x = x + 1 ということです。

5. 多段対応

元の例に適用するとエラーになります。

let ret   x   = fun _ -> x
let (>>=) m f = fun x -> f (m x) ()

let test =
    (fun x -> x + 1) >>= fun a ->
    (fun x -> x * 2) >>= fun b ->
    ret (a, b)

do
    printfn "%A" (test 3)
    printfn "%A" (test 5)

エラー内容

Test.fsx(6,19): error FS0001: The type 'int' does not match the type 'unit'
Test.fsx(6,17): error FS0043: The type 'int' does not match the type 'unit'
Test.fsx(10,19): error FS0039: The value or constructor 'test' is not defined
Test.fsx(11,19): error FS0039: The value or constructor 'test' is not defined

最初のエラーに注目します。(fun x -> x * 2)のxに()が渡されるため、x * 2の計算ができずにエラーになっています。

構造を単純化して考える

具体的なコードだと分かりにくいので、構造を単純化して1段と2段を比較します。

m >>= ret
m1 >>= (fun x -> (m2 >>= ret))

1のreturnに相当する部分が、2では(fun x -> (m2 >>= ret))となっています。f (m x) () で渡される()が1と2でどのように扱われているかを比較します。

1では m を評価した値が ret に渡されて、ret 内部で作られた関数 fun _ -> x が返されます。それに対して () を渡しても捨てられるため問題化しません。

2では m1 を評価した値が (fun x -> (m2 >>= ret)) に渡されて、-> の右に記述された式 m2 >>= ret が返されます。m2 >>= ret は何か値を与えると計算する関数になるため、計算できない値 () を渡すとエラーになります。m2 >>= ret にも外部から渡された引数をそのまま渡す必要があります。

以上より>>=を次のように修正すれば良いことが分かります。

F#（修正箇所）

let (>>=) m f = fun x -> f (m x) x

例に戻る

修正を元の例に適用してみます。

let ret   x   = fun _ -> x
let (>>=) m f = fun x -> f (m x) x

let test =
    (fun x -> x + 1) >>= fun a ->
    (fun x -> x * 2) >>= fun b ->
    ret (a, b)

do
    printfn "%A" (test 3)
    printfn "%A" (test 5)

実行結果

(4, 6)
(6, 10)

うまく動きました。

f (m x) x の最後の x は、>>= で連結された次の式に回されるのに使われます。階層構造ではなくフラットに捉えて、最初の >>= から次の >>= へのバトンだとイメージするのが良いでしょう。

6. ビルダーを実装

ビルダーを実装すれば、コンピュテーション式が使えるようになります。

let ret   x   = fun _ -> x
let (>>=) m f = fun x -> f (m x) x

type FuncBuilder() =
    member __.Return(x)  = ret x
    member __.Bind(m, f) = m >>= f
let func = FuncBuilder()

let test = func {
    let! a = fun x -> x + 1
    let! b = fun x -> x * 2
    return (a, b) }

do
    printfn "%A" (test 3)
    printfn "%A" (test 5)

実行結果

(4, 6)
(6, 10)

今まで作って来た>>=とretとの関係を示すためビルダーから使っていますが、いきなりビルダーで実装しても構いません。

type FuncBuilder() =
    member __.Return(x)  = fun _ -> x
    member __.Bind(m, f) = fun x -> f (m x) x
let func = FuncBuilder()

Stateモナド

関数モナドでは外部から渡された値は変化せずにバトンとして渡されましたが、それを変化させることを考えます。以後、通例に従って「バトン」ではなく「状態」と呼びます。

1. Haskellの例

Haskell

import Control.Monad.State

test = do
    a <- get
    put (a * 2)
    b <- get
    return (a, b)

main = do
    print (evalState test 3)
    print (evalState test 5)

実行結果

(3,6)
(5,10)

関数モナドはtestに直接値を渡せば評価できましたが、StateモナドではevalStateの力を借りています。

getは状態を取得するアクションです。状態はputによって書き替えることが可能です。

2. doを剥がす

Haskell

test =
    get         >>= \a ->
    put (a * 2) >>= \_ ->
    get         >>= \b ->
    return (a, b)

<-を書かない行は形式的に_に渡して捨てます。それ専用の>>という演算子もありますが、>>=で統一的に記述するため今回は使用しません。

※ コンピュテーション式ではdo!と書きます。後で使います。

3. returnを実装

形式上evalStateを経由してはいますが、まだ関数モナドと同じです。

let evalState m = m

let ret x = fun _ -> x

let test = ret 8

do
    printfn "%A" (evalState test 3)
    printfn "%A" (evalState test 5)

実行結果

8
8

4. 1段で>>=を実装

まずgetを確認します。まだ関数モナドと同じです。

let evalState m = m
let get = id

let ret   x   = fun _ -> x
let (>>=) m f = fun x -> f (m x) x

let test = get >>= ret

do
    printfn "%A" (evalState test 3)
    printfn "%A" (evalState test 5)

実行結果

3
5

5. 多段対応

putを混ぜてみます。

let ret   x   = fun _ -> x
let (>>=) m f = fun x -> f (m x) x

let evalState m = m
let get = id
let put = ret

let test =
    get         >>= fun a ->
    put (a * 2) >>= fun _ ->
    get         >>= fun b ->
    ret (a, b)

do
    printfn "%A" (evalState test 3)
    printfn "%A" (evalState test 5)

実行結果

(3, 3)
(5, 5)

putがうまく機能していません。

修正

次の>>=に渡される状態が元のままになっているため、(m x)の戻り値を使います。

F#（修正箇所）

let (>>=) m f = fun x ->
    let y = m x
    f y y

実行結果

(3, 6)
(5, 10)

うまく動きました。

値と状態の分離

実はまだStateモナドとしては不完全です。

Haskellでは次のようなことが可能です。

Haskell

import Control.Monad.State

postInc = do
    x <- get
    put (x + 1)
    return x

test2 = do
    a <- postInc
    b <- postInc
    return (a, b)

main = do
    print (evalState test2 3)
    print (evalState test2 5)

実行結果

(3,4)
(5,6)

postIncで状態を更新しますが、returnされるのは更新前の値です。

※ C言語などの i++ をイメージしています。

`do`を剥がす

Haskell

postInc =
    get         >>= \x ->
    put (x + 1) >>= \_ ->
    return x

test2 =
    postInc >>= \a ->
    postInc >>= \b ->
    return (a, b)

不具合

これをF#で試すとうまく動きません。

let ret   x   = fun _ -> x
let (>>=) m f = fun x ->
    let y = m x
    f y y

let evalState m = m
let get = id
let put = ret

let postInc =
    get         >>= fun x ->
    put (x + 1) >>= fun _ ->
    ret x

let test2 =
    postInc >>= fun a ->
    postInc >>= fun b ->
    ret (a, b)

do
    printfn "%A" (evalState test2 3)
    printfn "%A" (evalState test2 5)

実行結果

(3, 3)
(5, 5)

値と状態を分離していないため、postInc から返された値がそのまま状態として使われてしまい、インクリメントが打ち消されています。

修正

値と状態を分離して、タプルで受け渡すようにします。変更は以下のコードに押し込められるため、それを利用するコードは修正不要です。（外から見えるインターフェースに影響がないという意味です）

F#（修正箇所）

let ret   x   = fun s -> (x, s)
let (>>=) m f = fun s ->
    let (x, s') = m s
    f x s'

let evalState m s = fst (m s)
let get   = fun s -> (s , s)
let put s = fun _ -> ((), s)

実行結果

(3, 4)
(5, 6)

Haskellと同じ動きをするようになりました。

evalState以外の修正箇所では状態を受け取って値と状態のタプルを返しています。

状態 -> (値, 状態)

evalStateではタプルから値だけを返しています。

関数モナドではsに相当する部分が不変だったため、このように分離して管理する必要がありませんでした。

6. ビルダーを実装

putでは返される値()を捨てています。Haskellでは何も書かないと自動的に値が捨てられますが、F#ではdo!で明示します。

let ret   x   = fun s -> (x, s)
let (>>=) m f = fun s ->
    let (x, s') = m s
    f x s'

type StateBuilder() =
    member __.Return(x)  = ret x
    member __.Bind(m, f) = m >>= f
let state = StateBuilder()

let evalState m s = fst (m s)
let get   = fun s -> (s , s)
let put s = fun _ -> ((), s)

let test = state {
    let! a = get
    do! put (a * 2)
    let! b = get
    return (a, b) }

let postInc = state {
    let! x = get
    do! put (x + 1)
    return x }

let test2 = state {
    let! a = postInc
    let! b = postInc
    return (a, b) }

do
    printfn "%A" (evalState test  3)
    printfn "%A" (evalState test  5)
    printfn "%A" (evalState test2 3)
    printfn "%A" (evalState test2 5)

実行結果

(3, 6)
(5, 10)
(3, 4)
(5, 6)

関数モナドやStateモナドのように裏で状態を取り回すタイプは状態系モナドと呼ばれます。状態を扱うことはモナド共通の特徴というわけではなく、次に別のタイプを見ます。

リストモナド

関数はモナドとして扱えましたが、リストもモナドとして扱えます。

今まで見て来た状態系モナドとは異なるタイプです。状態を引き回すことはしません。

リストモナドはループを扱うことができます。

1. Haskellの例

Haskell

test = do
    a <- [1, 2, 3]
    b <- [4, 5, 6]
    return (a * b)

main = do
    print test

実行結果

[4,5,6,8,10,12,12,15,18]

リストからの値の取り出しが値を1つずつ取り出すループに変換されます。フラットに書いていますが二重ループです。F#で動作を真似たものと見比べてみてください。

let test =
    let list = System.Collections.Generic.List<int>()
    for a in [1; 2; 3] do
        for b in [4; 5; 6] do
            list.Add(a * b)
    Seq.toList list

do
    printfn "%A" test

実行結果

[4; 5; 6; 8; 10; 12; 12; 15; 18]

コンピュテーション式でHaskellの挙動を再現することを目指します。

※ HaskellからF#に変換するとき、リストの区切りを,から;に書き替える必要があります。,のままだとタプルが入った1要素のリストになってしまいます。

2. doを剥がす

Haskell

test =
    [1, 2, 3] >>= \a ->
    [4, 5, 6] >>= \b ->
    return (a * b)

3. returnを実装

要素が1つのリストを返します。

let ret x = [x]

let test = ret 1

do
    printfn "%A" test

実行結果

[1]

4. 1段で>>=を実装

ループを意識して実装します。

let ret x = [x]
let (>>=) (m:'a list) f =
    let list = System.Collections.Generic.List<'a>()
    for x in m do
        list.AddRange(f x)
    Seq.toList list

let test = [1; 2; 3] >>= ret

do
    printfn "%A" test

実行結果

[1; 2; 3]

5. 多段対応

そのまま試してみます。

let ret x = [x]
let (>>=) (m:'a list) f =
    let list = System.Collections.Generic.List<'a>()
    for x in m do
        list.AddRange(f x)
    Seq.toList list

let test =
    [1; 2; 3] >>= fun a ->
    [4; 5; 6] >>= fun b ->
    ret (a * b)

do
    printfn "%A" test

実行結果

[4; 5; 6; 8; 10; 12; 12; 15; 18]

すんなり動きました。

6. ビルダーを実装

let ret x = [x]
let (>>=) (m:'a list) f =
    let list = System.Collections.Generic.List<'a>()
    for x in m do
        list.AddRange(f x)
    Seq.toList list

type ListMonadBuilder() =
    member __.Return(x)  = ret x
    member __.Bind(m, f) = m >>= f
let listMonad = ListMonadBuilder()

let test = listMonad {
    let! a = [1; 2; 3]
    let! b = [4; 5; 6]
    return a * b }

do
    printfn "%A" test

実行結果

[4; 5; 6; 8; 10; 12; 12; 15; 18]

コンピュテーション式だけを見れば、forなしでループが実現されているように見えます。

空のリスト

空のリストを与えると、後続の処理が行われません。

F#（変更箇所）

let test = listMonad {
    let! a = [1; 2; 3]
    let! b = []
    return a * b }

実行結果

[]

空のリストを与えてもループの中に入らないと解釈できます。

let test =
    let list = System.Collections.Generic.List<int>()
    for a in [1; 2; 3] do
        for b in [] do       // 空のリスト
            list.Add(a * b)  // 中に入らない
    Seq.toList list

do
    printfn "%A" test

実行結果

[]

この性質の応用として、コンピュテーション式の途中でわざと空のリストを与えて途中脱出に使えます。

Maybeモナド

「1個までしか要素が持てないリスト」に相当するモナドです。個数が制限されている以外の挙動は基本的に同じです。

HaskellとF#では表記が若干異なるので比較します。F#では option 型を使用します。

Haskell	0個	1個	2個	3個	4個以上
リスト	`[]`	`[x]`	`[x, y]`	`[x, y, z]`	（略）
`Maybe`	`Nothing`	`Just x`	なし	なし	なし

F#	0個	1個	2個	3個	4個以上
リスト	`[]`	`[x]`	`[x; y]`	`[x; y; z]`	（略）
`option`	`None`	`Some x`	なし	なし	なし

0個は値がありませんが、これにより関数が評価に失敗して値を返せないことが表現できます。

1. Haskellの例

Nothingから値を取り出そうとしても失敗して、処理が途中で打ち切られます。空のリストで途中脱出になるのと同じだと考えれば良いでしょう。

Haskell

fact 0 = Just 1
fact n | n > 0 = do n' <- fact (n - 1); return (n * n')
       | otherwise = Nothing

facts n = do
    a <- fact  n
    b <- fact (n - 1)
    c <- fact (n - 2)
    return (a, b, c)

main = do
    print (facts 3)
    print (facts 2)
    print (facts 1)  -- cで失敗
    print (facts 0)  -- bで失敗

実行結果

Just (6,2,1)
Just (2,1,1)
Nothing
Nothing

2. doを剥がす

Haskell

fact 0 = Just 1
fact n | n > 0 = fact (n - 1) >>= \n' -> return (n * n')
       | otherwise = Nothing

facts n =
    fact  n      >>= \a ->
    fact (n - 1) >>= \b ->
    fact (n - 2) >>= \c ->
    return (a, b, c)

3. returnを実装

Someに入れるだけです。

let ret x = Some x

let test = ret 1

do
    printfn "%A" test

実行結果

Some 1

4. 1段で>>=を実装

要素数は0か1なので、ループとして処理する必要はありません。

let ret x = Some x
let (>>=) (m:'a option) f =
    match m with
    | Some x -> f x
    | None   -> None

let test = Some 1 >>= ret

do
    printfn "%A" test

実行結果

Some 1

fを評価しないことで、処理を途中で打ち切ることになります。

5. 多段対応

そのまま試してみます。

let ret x = Some x
let (>>=) (m:'a option) f =
    match m with
    | Some x -> f x
    | None   -> None

let rec fact = function
| 0            -> Some 1
| n when n > 0 -> fact (n - 1) >>= fun n' -> ret (n * n')
| _            -> None

let facts n =
    fact  n      >>= fun a ->
    fact (n - 1) >>= fun b ->
    fact (n - 2) >>= fun c ->
    ret (a, b, c)

do
    printfn "%A" (facts 3)
    printfn "%A" (facts 2)
    printfn "%A" (facts 1)  // cで失敗
    printfn "%A" (facts 0)  // bで失敗

実行結果

Some (6, 2, 1)
Some (2, 1, 1)
<null>
<null>

Noneは<null>と表示されていますが、すんなり動きました。

6. ビルダーを実装

let ret x = Some x
let (>>=) (m:'a option) f =
    match m with
    | Some x -> f x
    | None   -> None

type MaybeBuilder() =
    member __.Return(x)  = ret x
    member __.Bind(m, f) = m >>= f
let maybe = MaybeBuilder()

let rec fact = function
| 0            -> Some 1
| n when n > 0 -> maybe { let! n' = fact (n - 1) in return (n * n') }
| _            -> None

let facts n = maybe {
    let! a = fact  n
    let! b = fact (n - 1)
    let! c = fact (n - 2)
    return (a, b, c) }

do
    printfn "%A" (facts 3)
    printfn "%A" (facts 2)
    printfn "%A" (facts 1)  // cで失敗
    printfn "%A" (facts 0)  // bで失敗

実行結果

Some (6, 2, 1)
Some (2, 1, 1)
<null>
<null>

let!のタイミングで失敗がチェックされて、失敗していたら途中で打ち切られます。

おわりに

いくつかモナドをコンピュテーション式で実装して来ました。複雑なコードは一気に書けないので、なるべく直感的に少しずつ書く過程を示そうと試みました。ReturnとBindだけで色々な処理が表現できることが分かれば、まずは十分ではないでしょうか。

ここに示したものはどれも基本的なモナドばかりです。ある程度は慣れておけば、新しい発想のタネともなるのではないでしょうか。

コンピュテーション式でモナドを作ってみる

モナド

モナド則

オペランド

コンピュテーション式

作業手順

関数モナド

1. Haskellの例

2. doを剥がす

3. returnを実装

4. 1段で>>=を実装

5. 多段対応

構造を単純化して考える

例に戻る

6. ビルダーを実装

Stateモナド

1. Haskellの例

2. doを剥がす

3. returnを実装

4. 1段で>>=を実装

5. 多段対応

修正

値と状態の分離

doを剥がす

不具合

修正

6. ビルダーを実装

リストモナド

1. Haskellの例

2. doを剥がす

3. returnを実装

4. 1段で>>=を実装

5. 多段対応

6. ビルダーを実装

空のリスト

Maybeモナド

1. Haskellの例

2. doを剥がす

3. returnを実装

4. 1段で>>=を実装

5. 多段対応

6. ビルダーを実装

おわりに

`do`を剥がす