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

この記事はC# Advent Calendar 2019の12月５日の記事として書かれました。

この記事はkekyoさんのスライド「C#でわかる こわくないMonad」をモチベーションに書かれています。
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」で大変詳しく紹介されています。
本記事ではHaskellの入門者である『すごいHaskellたのしく学ぼう!』に掲載されているモナドのうち幾つかについて簡単に紹介しつつ、適切な実装を与えることでHaskellのdo記法に似たことがC#のクエリ構文でもできることを例示します。そして、その実装がC#で記述量的にそこまで重くないことを確認します。

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

前提知識

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

Haskellのモナド＋do記法とは

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

実例

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

使われ方

List モナド

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

Haskellでの例

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記法に対応していると考えることができます。

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を求めて出力しています。

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クラスを定義してやれば以下のように書くことができます。

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での例

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クラスを定義してやれば以下のように書くことができます。

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での例

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クラスを定義して、以下のように書けます。

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での例

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クラスを定義して、以下のようにすることができます。
例示の都合上、Stackクラスも定義しています。

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としたときに拡張メソッド方式でSelectとSelectManyを書くと、各メソッドのシグネチャと返り値の型は

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の型の書き方では

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

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

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

であり。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>クラスとそのサブクラスを以下のように定義します。

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を定めます。

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クラスを定義します。

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

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

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モナド

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

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

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モナド

class State<TState, T>
{
    public Func<TState, (TState, T)> F { get; }
    public State(Func<TState, (TState, T)> f) => F = f;
}

に対して、

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風言語のインタプリタを実装する」で紹介していたSpracheというパーサコンビネータはクエリ記法で書けるように設計されています。
たとえば if e1 then e2 else e3という式をパースするパーサーは

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

まとめ

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

今回書いたコードのリンクはこちらです。
読んでいただきありがとうございました。皆様に幸せな年末がありますように！