C#のクエリ記法をHaskellのモナド＆do記法みたいに使う話

この記事は[C# Advent Calendar 2019](https://qiita.com/advent-calendar/2019/c-sharp)の12月５日の記事として書かれました。

この記事はkekyoさんのスライド[「C#でわかる こわくないMonad」](https://www.slideshare.net/kekyo/cm-76399518)をモチベーションに書かれています。
kekyoさんのスライドでは、HaskellのMaybeモナド(Optionモナド)に相当するクラスを、まるでHaskellのdo記法のようにC#のクエリ記法で扱う方法が丁寧に紹介されています。本記事ではその他のモナドも同様の手法を用いて実装していきます。

# TL; DR

- C#のクエリ記法でHaskellのモナド & do 記法みたいな機能が実現できるよ！
- 簡単な実装でそれを実現できるよ！
- この手法が用いられたプロダクトもあるので紹介するよ！

# 概要

LINQでおなじみのクエリ記法(`from ... in ... select ...`)ですが、これを用いてHaskellのモナド＆Do記法に近い書き方がC#でもできることを紹介します。

HaskellでおなじみのモナドのうちMaybeモナド(Optionモナド) & do記法をC#で再現する方法については、既にkekyoさんのスライド[「C#でわかる こわくないMonad」](https://www.slideshare.net/kekyo/cm-76399518)で大変詳しく紹介されています。
本記事ではHaskellの入門者である[『すごいHaskellたのしく学ぼう!』](https://www.amazon.co.jp/dp/4274068854/ref=cm_sw_r_tw_dp_U_x_--o5DbR95AJHD)に掲載されているモナドのうち幾つかについて簡単に紹介しつつ、適切な実装を与えることでHaskellのdo記法に似たことがC#のクエリ構文でもできることを例示します。そして、その実装がC#で記述量的にそこまで重くないことを確認します。

kekyoさんのスライドでも触れられている通り、C#でわざわざこの書き方をする意義は多くの場合あまりなさそうです。しかし、この手法が効果的に使われている[Sprache](https://github.com/sprache/Sprache)というプロダクトがあります。最後にそのプロダクトがどのようにクエリ構文を活用しているか簡単に紹介します。

# 前提知識

HaskellやHaskellのモナドの知識は特に仮定しません。Haskellのコードが出てきたときは解説を入れます。漠然とコードを眺めて「Haskellのdo記法と似た書き方がとC#でもできるのだなあ」と納得していだければ筆者の目的は達成します。

# Haskellのモナド＋do記法とは

文脈を伴う計算を簡単な構文で貼り合わせて大きな単位にしていける機能...などと言葉を尽くしたいところですが、おそらく自然言語で言葉を尽くすより以下の実例を見たほうが直感が得られやすいと思います。
この辺りの話については、[『すごいHaskellたのしく学ぼう!』](https://www.amazon.co.jp/dp/4274068854/ref=cm_sw_r_tw_dp_U_x_--o5DbR95AJHD)という本にわかりやすい例と詳しい説明があるので、興味のある方はそちらの本でHaskellに触れてみてもいいかもしれません。

# 実例
以下ではHaskellのモナド & Do記法の例とそれに対応するC#のコードを幾つか見ていきます。
まず、それぞれのモナドに対して使われ方を確認します。
C#のクエリ記法で同様の書き方をするために必要となる実装は、最後にまとめて確認します。

## 使われ方

### List モナド

Listモナドにおける文脈は「複数の可能性」です。Listモナドは、可能なケースの組み合わせ全てに対して答えを返すときに有用です。以下のHaskellでの例を見てみましょう。

#### Haskellでの例

```hs
allPossibility :: [Int]
allPossibility = do
    sgn <- [-1, 1]
    a <- [1, 2, 3]
    b <- [4, 5]
    return $ sgn * (10 * a + b)

main :: IO ()
main = print allPossibility
```

sgnは-1と1の可能性があり、aは1と2と3の可能性があり、bは4と5の可能性があります。
これに対して、`sgn * (10 * a + b)`という計算をしようとしています。

実行すると以下の出力を得ます。

```
[-14,-15,-24,-25,-34,-35,14,15,24,25,34,35]
```

可能な組み合わせ全てを網羅した結果がリストとして得られます。

#### C#での例

我々が見慣れているC# での IEnumerableに対するクエリ構文は、HaskellのListモナドに対するdo記法に対応していると考えることができます。

```csharp
var allPossibility =
    from sgn in new int[] { -1, 1 }
    from a in new int[] { 1, 2, 3 }
    from b in new int[] { 4, 5 }
    select sgn * (10 * a + b);

allPossibility.ToList().ForEach(x => Console.Write($"{x} ");
```

実行すると、同じく全ての可能性を網羅した以下の出力を得ます。

```
-14 -15 -24 -25 -34 -35 14 15 24 25 34 35 
```

Haskellのdo記法を用いた書き方と近い書き方ができています。

### Maybe モナド

Maybeモナドにおける文脈は「失敗する可能性」「値が無い可能性」です。
Maybeモナドは失敗する可能性のある計算を張り合わせるときに用いられます。
こちらもHaskellでの例を通じて説明します。

#### Haskell での例

`Maybe Int型`はC#の`int?`に似た型です。
何らかの値が入っているかもしれませんし(`Just n`)、値が入っていないかもしれません(`Nothing`)。

以下のコードのsumThreeは、Maybe Int型の３つ組を受け取ってそれらの和を返そうとする関数です。
mainではtestCasesの中の各test caseに対して、そのsumThreeを求めて出力しています。

```hs
sumThree :: (Maybe Int, Maybe Int, Maybe Int) -> Maybe Int
sumThree (ma, mb, mc) = do
    a <- ma
    b <- mb
    c <- mc
    return $ a + b + c

testCases = [
    (Just 1, Just 2, Just 3),
    (Nothing, Just 2, Just 3),
    (Just 1, Nothing, Just 3),
    (Just 1, Just 2, Nothing),
    (Nothing, Nothing, Nothing)
    ]

main :: IO ()
main = mapM_ (print . sumThree) testCases
```

結果は

```
Just 6
Nothing
Nothing
Nothing
Nothing
```

となります。ma, mb, mcが全て`Just n`だったときのみ計算は成功し、目的の値を返します。
どれか一つでも`Nothing`だった場合、計算は失敗し、`Nothing`を返します。

#### C#での例

C#ではうまくMaybe<T>クラスを定義してやれば以下のように書くことができます。

```csharp
Maybe<int> sumThree(Maybe<int> ma, Maybe<int> mb, Maybe<int> mc) =>
    from a in ma
    from b in mb
    from c in mc
    select a + b + c;

var testCases = new List<(Maybe<int>, Maybe<int>, Maybe<int>)>{
    (Just(1), Just(2), Just(3)),
    (Nothing, Just(2), Just(3)),
    (Just(1), Nothing, Just(3)),
    (Just(1), Just(2), Nothing),
    (Nothing, Nothing, Nothing),
};

testCases.ForEach(testCase =>
{
    var (ma, mb, mc) = testCase;
    Console.WriteLine($"{ma} + {mb} + {mc} = {sumThree(ma, mb, mc)}");
});
```

Haskellでの例と同様に、以下の出力を得ます。

```
Just(1) + Just(2) + Just(3) => Just(6)
Nothing + Just(2) + Just(3) => Nothing
Just(1) + Nothing + Just(3) => Nothing
Just(1) + Just(2) + Nothing => Nothing
Nothing + Nothing + Nothing => Nothing
```

### Writerモナド
Writerモナドにおける文脈は「ロギング」です。なんらかのログをとりながら計算を進めていくことができます。

#### Haskellでの例

```haskell
import Control.Monad.Writer

sw :: Writer String Int
sw = do
    a <- writer (3, "a is 3. ")
    b <- writer (a + 4, "b is a + 4. ")
    c <- writer (a + b, "c is a + b. ")
    return c

main :: IO ()
main = print sw
```

これを実行すると、

```
WriterT (Identity (10,"a is 3. b is a + 4. c is a + b. "))
```

との出力を得ます。出力の仔細については今回見る必要はありません。
`a =3; b = a + 4: c = a + b`の計算結果である10と、そこに至るまでのログである`"a is 3. b is a + 4. c is a + b. "`の両方の情報が保持されていることが確認できます。

#### C#での例

こちらもうまくStringWriter<T>クラスを定義してやれば以下のように書くことができます。

```csharp
StringWriter<int> SW(int i, String s) => new StringWriter<int>(i, s);

var sw =
    from a in SW(3, "a is 3. ")
    from b in SW(b + 4, "b is a + 4. ")
    from c in SW(a + b, "c is a + b. ")
    select c;

Console.WriteLine($"value: {sw.Value}");
Console.WriteLine($"log: {sw.Log}");
```

こちらはStringに限ったWriterの実装にしています。（`+` をどう持つかなどを決めるのが面倒だったため）

出力は以下の通りです。


```
value: 10
log: a is 3. b is a + 4. c is a + b. 
```

### Readerモナド
Readerモナドにおける文脈は、全ての関数に共通して渡される引数です。言葉による説明では少しわかりづらいと思うので、Haskellでの例を見てみましょう。

#### Haskellでの例

```haskell
reader :: Int -> String
reader = do
    twice <- (* 2)
    len <- (length . show)
    plusHundred <- (+ 100)
    return $ "twice: " ++ show twice ++ ", length: " ++ show len ++ ", plus 100: " ++ show plusHundred

main :: IO ()
main = putStrLn $ r 15
```

main関数を見てみると、 readerという関数に15が渡されています。

readerの中では、引数を２倍する処理、引数を文字列化して文字列の長さを得る処理、100を足す処理の３つの処理全てに15が渡されます。
その結果、twiceには30が、lenには2が、plusHundredには115が入ります。

出力は以下の通りです。

```
twice: 30, length: 2, plus 100: 115
```

#### C#での例

Readerクラスを定義して、以下のように書けます。

```csharp
Reader<int, int> R(Func<int, int> f) => new Reader<int, int>(f);

var reader =
    from twice in R(x => x * 2)
    from len in R(x => x.ToString().Length)
    from plusHundred in R(x => x + 100)
    select $"twice: {twice}, length: {len}, plus 100: {plusHundred}";

Console.WriteLine(reader.F(15));
```

出力は以下の通りです。

```
twice: 30, length: 2, plus 100: 115
```


### Stateモナド

Stateモナドにおける文脈は状態です。
裏で状態を持ち回して使います。

C#では、例えば`currentState`のような変数を用意してその変数の値を書き換えていけば、状態を読み、変更して、下の行に伝播させることは容易です。
しかし、Haskellでは全ての変数はImmutableなので、変数を書き換える方法では状態を持ち回せません。そこで、状態を簡単に持ち回すためにStateモナドが用いられます。

#### Haskellでの例

```haskell
import Control.Monad.State

type Stack = [Int]

pop :: State Stack Int
pop = state $ \(x : xs) -> (x, xs)

push :: Int -> State Stack ()
push a = state $ \xs -> ((), a : xs)

f :: State Stack Int
f = do
    push 3
    push 1
    push 4
    push 1
    push 5
    push 9
    a <- pop
    b <- pop
    c <- pop
    return $ a + b + c

main :: IO ()
main = print $ runState f []
```

stackに、 3, 1, 4, 1, 5, 9を順番に積んでいき、3回popして、得られた値を足し合わせています。
最後に積まれた3つの値は1, 5, 9なので、和として15が出力され、 stackには最終的に一番上から順に4, 1, 3が積まれています。
以下は実行結果です。

```
(15,[4,1,3])
```

#### C#での例

State<T. S>クラスを定義して、以下のようにすることができます。
例示の都合上、Stack<T>クラスも定義しています。

```csharp
State<Stack<int>, int> pop() => new State<Stack<int>, int>(stack => stack.Pop());
State<Stack<int>, UnitType> push(int i) =>
    new State<Stack<int>, UnitType>(stack => (new Cons<int>(i, stack), Unit));

var f =
    from _1 in push(3)
    from _2 in push(1)
    from _3 in push(4)
    from _4 in push(1)
    from _5 in push(5)
    from _6 in push(9)
    from a in pop()
    from b in pop()
    from c in pop()
    select a + b + c;

var (state, result) = f.F(new Nil<int>());

Console.Write("state: ");
state.ToList().ForEach(x => Console.Write($"{x} "));
Console.WriteLine();
Console.WriteLine($"result: {result}");
```
現行のC#ではこの場面でdiscard`_`が使えないため、使わない値に一々`_1`, `_2`などと名前をつけています。

実行結果は以下の通りです。

```
state: 4 1 3 
result: 15
```

## 実装側

このセクションの目的は「クエリ構文をHaskellのdo記法みたいに使うためには、それほど大変な実装をする必要はなさそうだ」という雰囲気を掴んでもらうことにあります。したがって本セクションを細かく読んでいただく必要はありません。「このくらいの行数で済むのかー」くらいの読み方をしていただければ幸いです。

## Select & SelectMany v.s. Return & Bind

クエリ構文を上で紹介したように使うには、from の右側に来る値が`Select`メソッドと`SelectMany`メソッドを持っている必要があります。
この値の型をM<T1>としたときに拡張メソッド方式で`Select`と`SelectMany`を書くと、各メソッドのシグネチャと返り値の型は

```csharp
M<T2> Select<T1, T2>(this M<T1>, Func<T1, T2>)
M<T3> SelectMany<T1, T2, T3>(this M<T1>, Func<T1, Maybe<T2>>, Func<T1, T2, T3>)    
```
となります。

これはHaskellの型の書き方では

```haskell
select :: m t1 -> (t1 -> t2) -> m t2
selectMany :: m t1 -> (t1 -> m t2) -> (t1 -> t2 -> t3) -> m t3
```

に相当します。見ての通り`selectMany`が少し複雑です。
haskellのモナドを定義するには`return`と`bind`を定義すればよいのですが、これらはC#のシグネチャ＋返り値の型では

```csharp
M<T1> Return<T1>(T1 value)
M<T2> Bind<T1, T2>(M<T1>, Func<T1, Maybe<T2>>)
```

であり。Haskellの型では

```haskell
return :: t1 -> m t1
bind :: m t1 -> (t1 -> m t2) -> m t2 
```

となるような関数です。`Select` & `SelectMany`の組み合わせと比べると単純なのが見て取れると思います。
実は、クエリ構文をdo記法のように機能をさせるための`Select`と`SelectMany`は、`Return`と`Bind`の組み合わせによって実装できます。よって、簡単な方の組み合わせとして`Return`と`Bind`を使って説明していきます。

### Listモナド

今回自前で実装していないので説明は省略します。

### Maybeモナド

`Maybe<T>`クラスとそのサブクラスを以下のように定義します。

```csharp
abstract class Maybe<T>
{
    public static Maybe<T> Nothing => Nothing<T>.Instance;
    public static Maybe<T> Just(T value) => new Just<T>(value);
}
sealed class Nothing<T> : Maybe<T>
{
    private static Nothing<T> instance = new Nothing<T>();
    public static Nothing<T> Instance => instance;
    private Nothing() { }
    public override string ToString() => "Nothing";
}
sealed class Just<T> : Maybe<T>
{
    public T Value { get; }
    public Just(T value) => Value = value;
    public void Deconstruct(out T value) => value = Value;
    public override string ToString() => $"Just({Value})";
}
```

サブクラス関係によって、値がない状態`Nothing<T>`と値がある状態`Just<T>`を表現できていることがわかります。
これに対して以下のようにReturnとBindを定めます。

```csharp
public static Maybe<T> Return<T>(T value) => Maybe<T>.Just(value);
public static Maybe<T2> Bind<T1, T2>(Maybe<T1> x, Func<T1, Maybe<T2>> f) => x switch
{
    Nothing<T1> _ => Maybe<T2>.Nothing,
    Just<T1>(var v) => f(v)

};
```

Returnは受け取った値を特に何も処理せずにJustでくるんで返します。
Bindは受け取った値がNothing型かJust型かで場合分けし、Nothing型の場合はNothingを、Just型の場合は中の値を取り出し、その値に関数を適用して、再びJust型でくるんで返します。

### Writerモナド

ValueとLogを持つStringWriter<T>クラスを定義します。

```csharp
class StringWriter<T>
{
    public T Value { get; }
    public string Log { get; }
    public StringWriter(T value, String log = "") => (Value, Log) = (value, log);
}
```

これに対して以下のようにReturnとBindを定義します。

```csharp
public static StringWriter<T> Return<T>(T value) => new StringWriter<T>(value);
public static StringWriter<T2> Bind<T1, T2>(StringWriter<T1> sw, Func<T1, StringWriter<T2>> f)
{
    var sw2 = f(sw.Value);
    return new StringWriter<T2>(sw2.Value, sw.Log + sw2.Log);
}
```

やはりReturnはくるむだけです。特に説明することはありません。

### Readerモナド

```csharp

Reader<TIn, TOut>は関数を保持するクラスです。
class Reader<TIn, TOut>
{
    public Func<TIn, TOut> F { get; }
    public Reader(Func<TIn, TOut> f) => F = f;
}
```

これに対して以下のようにReturnとBindを定義します。

```csharp
public static Reader<TIn, T> Return<TIn, T>(T value) => new Reader<TIn, T>(_ => value);
public static Reader<TIn, T2> Bind<TIn, T1, T2>(Reader<TIn, T1> x, Func<T1, Reader<TIn, T2>> f) =>
    new Reader<TIn, T2>(y => f(x.F(y)).F(y));
```

Returnは値を受け取って、「引数を受け取るがその値を無視して常に決まった値を返す関数」を持ったReaderクラスの値を作ります。

### Stateモナド

```csharp
class State<TState, T>
{
    public Func<TState, (TState, T)> F { get; }
    public State(Func<TState, (TState, T)> f) => F = f;
}
```
に対して、

```csharp
public static State<TState, T> Return<TState, T>(T value) => new State<TState, T>(s => (s, value));
public static State<TState, T2> Bind<TState, T1, T2>(State<TState, T1> x, Func<T1, State<TState, T2>> f) =>
    new State<TState, T2>(st =>
    {
        var (newSt, v) = x.F(st);
        return f(v).F(newSt);
    });
```

で済みます。
いずれもかなり単純に実装できていることがお分かりいただけたかと思います。

# 実用の話

私が以前書いた記事の[「C#のパーサコンビネータライブラリSpracheでML風言語のインタプリタを実装する」](https://qiita.com/yuchiki1000yen/items/12a90e6fc728b900b376)で紹介していた[Sprache](https://github.com/sprache/Sprache)というパーサコンビネータはクエリ記法で書けるように設計されています。
たとえば `if e1 then e2 else e3`という式をパースするパーサーは

```csharp
Parser<Expr> IfParser =
    from ifToken in Parse.String("if").Token()
    from p1 in PrimaryParser
    from thenToken in Parse.String("then").Token()
    from p2 in PrimaryParser
    from elseToken in Parse.String("else").Token()
    from p3 in PrimaryParser
    select new IfExpr(p1, p2, p3);
```

のように書くことができます。
Parser<T>型は文字列をパースしてT型の値を生成するパーサーの型です。例中だとprimaryParserというパーサーから、あたかもパース結果の値を取り出してp1, p2, p3に束縛しているかのように処理を書くことができます。

# まとめ

- C#のクエリ記法で、Haskellのモナド ＆ do 記法相当の機能が実現できます。（C#においてわざわざこのように書いた方がいいケースはあまりなさそうにも思えますが...）
- 紹介した各モナドは記述量的にそこまで重くなく実装できます。
- クエリ記法を使うように設計されているプロダクトとして[Sprache](https://github.com/sprache/Sprache)があります。


今回書いたコードのリンクは[こちら](https://github.com/yuchiki/csmonad)です。
読んでいただきありがとうございました。皆様に幸せな年末がありますように！