「モナドのすべて」のMaybeモナドの例をF#で

All About MonadsにはMaybeモナドのサンプルとしてクローン羊の例が載っています（http://www.sampou.org/haskell/a-a-monads/html/meet.html#example1）。これをF#で書いてみました。もうすでに誰かやってるとは思いますが。

普通にやる

まずSheep型を定義します。

type Sheep = {
    name:string;
    parents:option<Sheep * Sheep>;
}

とっても簡潔ですね。（これを書いた後にHaskellの方のコードを読んだのですが、少し定義が違いますね）
次に、父親、母親を返す関数を作ります。

let father (x:Sheep) =
    match x.parents with
        | None -> None
        | Some (f,_) -> Some f

let mother (x:Sheep) =
    match x.parents with
        | None -> None
        | Some (_,m) -> Some m

では、「母方の祖父」を返す関数maternalGrandFatherを作ってみましょう。

let maternalGrandFather x =
    match mother x with
        | None -> None
        | Some m -> father m

まあまだ大丈夫です。では「"母方の祖父"の父さん」を返す関数だったら？

let mathersPaternalGrandFather x =
    match mother x with
        | None -> None
        | Some m -> match father m with
                        | None -> None
                        | Some gf -> father gf

だんだんネストが深くなってきました。いかにもバグが入りそうですね。もう一世代前とかになると絶対イヤです。

Option.bindを使う

こういう時に便利なOption.bindという関数があります。これは

(* val bind : f:('a -> 'b option) -> inp:'a option -> 'b option *)
let bind f inp =
    match inp with
    | None -> None
    | Some x -> f x

こんな感じで定義されていて、入力がNoneならNoneを返し、入力値があるなら関数を適用するとかそんな感じ？（あやふや）
ともかくこれを使うと、

let maternalGrandFather x =
    Option.bind father (mother x)

こんな感じになります。やった、すごいスッキリ！……って、なんか関数を書く順番逆になってませんか（mother→fatherの順に適用するのに書く順番はfather→mother）。さっきの方がよかったんじゃ……。
まあ、F#なら普通はパイプライン演算子を使います。

let maternalGrandFather x =
    Some x
    |> Option.bind mother
    |> Option.bind father

「"母方の祖父"の父さん」の方も簡単

let mathersPaternalGrandFather x =
    Some x
    |> Option.bind mother
    |> Option.bind father
    |> Option.bind father

コンピューテーション式を使う

（F#プログラマのためのMaybeモナド入門 - みずぴー日記や、ステップアップでわかるコンピューテーション式。TryWith や TryFinally などの実装にぜひ活用したい Delayと Run - Bug Catharsisを参考にしました）
とりあえず上のでもいいんですが、なんだかOptionがうるさい感じがします。F#ではコンピューテーション式という、こういうのを簡潔に書ける構文があります。
まず下準備。

type MaybeBuilder() =
    member this.Bind (x,f) = Option.bind f x
    member this.Return x = Some x

let maybe = new MaybeBuilder()

maybeを使うと、こう書けます。

let maternalGrandFather x = maybe{
    let! m = mother x
    let! gf = father m
    return gf
}

let mothersPaternalGrandFather x = maybe{
    let! m = mother x
    let! gf = father m
    let! ggf = father gf
    return ggf
}

とはいえ

ここまでえらそーに書いてきましたが、実は全然分かってません。今回のは似たようなMaybeモナドの活用記事があったから書けましたが、自力でこのような変換をすることはできません。なんか因数分解みたいですね。パターンを覚えればできるという。共通因数をくくりだすような、段階的に変換できるテクニックとかはないのかな？

bind関数

Option.bindみたいなのはbind関数と呼ばれていて、Haskellだと(>>=)であらわされる。モナドを入れ物とすると、入れ物が空だったら空のまま返して、物が入っていれば中のものをいろいろいじくってまた入れ物に入れる、という感じなんだろか？

最後に

今回書いたコードを。なお、羊の家系図はこんな感じ。

(* 親をあらわすタプルは(father, mother)とする。 *)
type Sheep = {
    name:string;
    parents:option<Sheep * Sheep>;
}

(* 羊を作成 *)
let alan = {name = "Alan"; parents = None;}
let alice = {name = "Alice"; parents = None;}
let bob = {name = "Bob"; parents = Some (alan, alice);}
let betty = {name = "Betty"; parents = None;}
let carl = {name = "Carl"; parents = None;}
let cathy = {name = "Cathy"; parents = Some (bob, betty);}
let chris = {name = "Chris"; parents = Some (bob, betty);}
let cindy = {name = "Cindy"; parents = None;}
let dorothy = {name = "Dorothy"; parents = Some (carl, cathy);}
let dan = {name = "Dan"; parents = Some (chris, cindy);}

let father (x:Sheep) =
    match x.parents with
        | None -> None
        | Some (f,_) -> Some f

let mother (x:Sheep) =
    match x.parents with
        | None -> None
        | Some (_,m) -> Some m

(* 表示用 *)
let printName = function
    | None -> printfn "not exist"
    | Some {name = n} -> printfn "%s" n

(* 普通の場合 *)
let mGF x =
    match mother x with
        | None -> None
        | Some m -> father m

let mPGF x =
    match mother x with
        | None -> None
        | Some m -> match father m with
                        | None -> None
                        | Some gf -> father gf

(* Option.bindを使用 *)
let mGF_Bind x =
    Some x
    |> Option.bind mother
    |> Option.bind father

let mPGF_Bind x =
    Some x
    |> Option.bind mother
    |> Option.bind father
    |> Option.bind father

(* コンピューテーション式を使う準備 *)
type MaybeBuilder() =
    member this.Bind (x,f) = Option.bind f x
    member this.Return x = Some x

let maybe = new MaybeBuilder()

(* コンピューテーション式を使用 *)
let mGF_Compute x  = maybe{
    let! m = mother x
    let! gf = father m
    return gf
}

let mPGF_Compute x = maybe{
    let! m = mother x
    let! gf = father m
    let! ggf = father gf
    return ggf
}

(* テスト *)
printfn "*Nornal(too deep nest)"
printf "    Dorothy's MGF -> "
printName (mGF dorothy)
printf "    Dorothy's MPGF -> "
printName (mPGF dorothy)
printf "    Don's MGF -> "
printName (mGF dan)
printf "    Don's MPGF -> "
printName (mPGF dan)
printfn ""

printfn "*Use 'Option.bind'"
printf "    Dorothy's MGF -> "
printName (mGF_Bind dorothy)
printf "    Dorothy's MPGF -> "
printName (mPGF_Bind dorothy)
printf "    Don's MGF -> "
printName (mGF_Bind dan)
printf "    Don's MPGF -> "
printName (mPGF_Bind dan)
printfn ""

printfn "*Use Computation expression"
printf "    Dorothy's MGF -> "
printName (mGF_Compute dorothy)
printf "    Dorothy's MPGF -> "
printName (mPGF_Compute dorothy)
printf "    Don's MGF -> "
printName (mGF_Compute dan)
printf "    Don's MPGF -> "
printName (mPGF_Compute dan)
printfn ""