Query Expression Pattern で Maybe monad を書く

Query Expression Pattern

C# 3.0 には Query expression pattern というものがあって，このパターンと同じ構造を持つ型はクエリ式に使うことができます．IEnumerable<T> かどうかは関係ありません．duck-typing みたいですね．

delegate R Func<T1,R>(T1 arg1);
delegate R Func<T1,T2,R>(T1 arg1, T2 arg2);
class C
{
   public C<T> Cast<T>();
}
class C<T>
{
   public C<T> Where(Func<T,bool> predicate);
   public C<U> Select<U>(Func<T,U> selector);
   public C<V> SelectMany<U,V>(Func<T,C<U>> selector,
      Func<T,U,V> resultSelector);
   public C<V> Join<U,K,V>(C<U> inner, Func<T,K> outerKeySelector,
      Func<U,K> innerKeySelector, Func<T,U,V> resultSelector);
   public C<V> GroupJoin<U,K,V>(C<U> inner, Func<T,K> outerKeySelector,
      Func<U,K> innerKeySelector, Func<T,C<U>,V> resultSelector);
   public O<T> OrderBy<K>(Func<T,K> keySelector);
   public O<T> OrderByDescending<K>(Func<T,K> keySelector);
   public C<G<K,T>> GroupBy<K>(Func<T,K> keySelector);
   public C<G<K,E>> GroupBy<K,E>(Func<T,K> keySelector,
      Func<T,E> elementSelector);
}
class O<T> : C<T>
{
   public O<T> ThenBy<K>(Func<T,K> keySelector);
   public O<T> ThenByDescending<K>(Func<T,K> keySelector);
}
class G<K,T> : C<T>
{
   public K Key { get; }
}

SelectMany の第 1 引数，Func<T,C<U>> selector ってところがモニャドっぽいですよね？ 失礼，かみました．
ちなみに SelectMany の戻り値の型ですが，原文では C<U> になっています．これは C<V> が正しいように思うので引用文では直してあります*1．
なお，ドキュメントにもあるとおり，上のパターンに従う型であれば，generic struct や generic interface でも構いませんし，non-generic な型ですら実は OK です．本当にメソッドのパターンマッチで動いてます．さらに Extension Method もルックアップの対象になります．まさに何でもありです．

Maybe monad を書く

とりあえず軽い方がいいかなということで generic struct で書いてみました．まあ lambda 使いまくっておいてそれを気にするかという感じですが．面倒なのでいきなりコードを載せます．

using System;
using System.Linq;
using System.Diagnostics;

public static partial class Make
{
    public static Maybe<T> Maybe<T>(T value)
    {
        return new Maybe<T>(value);
    }
    public static Maybe<T> Maybe<T>(T? value) where T : struct
    {
        return value.HasValue ? new Maybe<T>(value.Value) : new Maybe<T>();
    }
}

[DebuggerDisplay("{IsNothing ? (object)\"Nothing\" : (object)Unwrap()}")]
public partial struct Maybe<T>
{
    private readonly T Value;
    private bool _hasValue;
    public Maybe(T value)
    {
        Value = value;
        _hasValue = (value != null);
    }
    public bool IsNothing { get { return !_hasValue; } }
    public T Unwrap() { return Value; }
    public static explicit operator T(Maybe<T> maybe) { return maybe.Unwrap(); }

    public Maybe<U> Select<U>(Func<T, U?> func) where U : struct
    {
        return this.IsNothing ? new Maybe<U>() : Make.Maybe<U>(func(this.Unwrap()));
    }
    public Maybe<U> Select<U>(Func<T, U> func)
    {
        return this.IsNothing ? new Maybe<U>() : Make.Maybe<U>(func(this.Unwrap()));
    }
    public Maybe<U> SelectMany<U>(Func<T, Maybe<U>> func)
    {
        return this.IsNothing ? new Maybe<U>() : func(this.Unwrap());
    }
    public Maybe<V> SelectMany<U, V>(Func<T, Maybe<U>> func, Func<T, U, V> resultSelector)
    {
        if( this.IsNothing ) return new Maybe<V>();
        var rawT = this.Unwrap();
        var temp = func(rawT);
        return temp.IsNothing ? new Maybe<V>() : new Maybe<V>(resultSelector(rawT, temp.Unwrap()));
    }
    public override string ToString()
    {
        return this.IsNothing ? "[" + typeof(T).Name + "] Nothing" : ((T)this).ToString();
    }
}

参照型および Nullable については null を「Nothing」と定義しています．
Select と SelectMany しか実装していませんが，これしか使わないクエリ式であれば問題ありません．ますます適当ですね．
まあ他のは list monad 専用な感じですし*2，今回はこれで OK としましょう．

使ってみる (メソッドチェイン編)

var length = Make.Maybe(new Random())
                 .Select(r => r.Next())
                 .Select(i => i % 2 == 0 ? i.ToString() : default(string))
                 .Select(s => s.Length);

Console.WriteLine(length.IsNothing);

// 下の2つは同じ意味
Console.WriteLine(length.Unwrap());
Console.WriteLine((int)length);

結果 1

False
10
10

結果 2

True
0
0

途中確率 2 分の 1 で null が後段に渡される感じの連鎖処理です．最終段の s.Length で null チェック面倒だよねみたいな雰囲気をお察し下さい．IsNothing が true を返したときに Unwrap しても例外は投げないようになっています．まあこの辺の仕様はお好みでという感じで．

使ってみる (クエリ式編)

ではクエリ式で使えるところも見てみましょう．

var length =
    from r in Make.Maybe(new Random())
    from i in Make.Maybe(r.Next())
    from str in Make.Maybe(i % 2 == 0 ? i.ToString() : default(string))
    from len in Make.Maybe(str.Length)
    select len;

SelectMany を実装したので，透過識別子を裏で勝手に作ってくれたり lambda の矢印を消し去ったりというシンタックスシュガーの恩恵を受けられます．

他の実装

今回作った Maybe は作られた瞬間に状態を確定させてますが，IEnumerable<T> のように毎回値を取り出すときに再計算するような戦略と混ぜてしまうのもありかもしれません．

じゃあ Expression Tree は？

残念ですが，IQueryProvider.CreateQuery<TElement> は IQueryable<TElement> と結びついていて，IQueryable<TElement> は IEnumerable<TElement> のサブタイプなので，そこはアヒルっぽくはいかないんじゃないかと思います．

*1:『Linq in Action』(初版) の 12.3.2 にも同じコードがあるのですが，こちらも C<U> になっていて原文コピペっぽいです

*2:でも guard として Where はあってもいい気がしてきた