LINQ のクエリ パターン

Visual Studio で C# のプロジェクト (ここではコンソール アプリケーションにしています) を作成して、
次のようなクエリ式を書いてみます。

Program.cs


class Program
{
    static void Main(string[] args)
    {
        var result =
            from x in new Monad<int>()
            select x;
    }
}

public class Monad<T>
{
}


Monad<T> はとりあえず空のジェネリック クラスです。
この状態でビルドすると、

「ソース型 ○○ のクエリ パターンの実装が見つかりませんでした。’Select’ が見つかりません。」

というコンパイラ エラーになります。

コンパイラ エラー CS1936

 

このクエリ パターンとは LINQ 標準クエリ演算子のことで、具体的には Select, Where, OrderBy メソッドなどがあります。
標準クエリ演算子のクエリ式構文に対応が記載されており、
例えば C# で select 句が有効になるようにするには、
IEnumerable<T> でいうところの Enumerable.Select メソッドに相当するメソッドが実装されている必要があります。

 

というわけで、例として Maybe モナドとそのクエリ パターンを実装してみます。

Maybe.cs


public struct Maybe<T>
{
    public static readonly Maybe<T> None = new Maybe<T>();

    T _value;

    public T Value
    {
        get
        {
            if (!HasValue) throw new InvalidOperationException();
            return _value;
        }
    }

    public bool HasValue { get; private set; }

    public Maybe(T value)
        : this()
    {
        _value = value;
        HasValue = true;
    }

    public static explicit operator T(Maybe<T> value)
    {
        return value.Value;
    }

    public static implicit operator Maybe<T>(T value)
    {
        return new Maybe<T>(value);
    }

    public Maybe<TResult> Bind<TResult>(Func<T, Maybe<TResult>> func)
    {
        return HasValue
            ? func(_value)
            : Maybe<TResult>.None;
    }

    public override string ToString()
    {
        return HasValue
            ? _value.ToString()
            : "";
    }
}

public static class Maybe
{
    public static Maybe<T> ToMaybe<T>(this T value)
    {
        return value;
    }

    public static Maybe<TResult> Select<T, TResult>(this Maybe<T> maybe, Func<T, TResult> selector)
    {
        return maybe.HasValue
            ? selector((T)maybe)
            : Maybe<TResult>.None;
    }

    public static Maybe<TResult> SelectMany<T, U, TResult>(this Maybe<T> maybe, Func<T, Maybe<U>> selector, Func<T, U, TResult> resultSelector)
    {
        var selected = maybe.Bind(selector);
        return selected.HasValue
            ? resultSelector((T)maybe, (U)selected)
            : Maybe<TResult>.None;
    }

    public static Maybe<T> Where<T>(this Maybe<T> maybe, Func<T, bool> predicate)
    {
        return maybe.HasValue && predicate((T)maybe)
            ? maybe
            : Maybe<T>.None;
    }
}


Select メソッドのほか、

  • 複数の from 句に相当する SelectMany メソッド
  • where 句に相当する Where メソッド

を実装しています。
このようにクエリ パターンを実装しておくと、次のようにクエリ式を書くことができます。

Program.cs


class Program
{
    static void Main(string[] args)
    {
        var result1 = Add(1, 2); // 3
        var result2 = Add(2, 1); // None
        var result3 = Add(1, Maybe<int>.None); // None
    }

    static Maybe<int> Add(Maybe<int> x, Maybe<int> y)
    {
        return
            from _x in x
            from _y in y
            where _x < _y
            select _x + _y;
    }
}


 

このようにして、IEnumerable<T> インターフェイス以外でもクエリ式を利用することができます。
ちなみに、IObservable<T> インターフェイスのクエリ式については、
Reactive Extensionsの概要と利用方法にコード例が載っています。

 

作成したサンプル
MonadConsole (GitHub)

参照
コンパイラ エラー CS1936
標準クエリ演算子の概要
select 句 (C# リファレンス)
Query Expression Pattern で Maybe monad を書く
モナドの驚異

広告

F# で素数を求める

以前に LINQ で素数を求める (C#) という記事を書きましたが、
その中にある GetPrimeNumbers 関数を F# で書いてみると、次のようになります。

 

Program.fs


open System
open System.Collections.Generic
open System.Diagnostics

module Seq2 =
    let do2 action source =
        seq {
            for x in source do
                action(x)
                yield x
        }

let getPrimeNumbers minValue maxValue =
    (
        new List<int64>(),
        Math.Max(minValue, 2L),
        Math.Max(maxValue, 0L),
        if maxValue >= 0L then (maxValue |> float |> Math.Sqrt |> int64) else 0L
    )
    |> Seq.singleton
    |> Seq.collect (fun (primes, min, max, root_max) ->
        (seq { 2L .. Math.Min(root_max, min  1L) }, seq { min .. max })
        ||> Seq.append
        |> Seq.map (fun i -> (primes, i, i |> float |> Math.Sqrt |> int64)))
    |> Seq.filter (fun (primes, i, root_i) ->
        primes
        |> Seq.takeWhile (fun p -> p <= root_i)
        |> Seq.forall (fun p -> i % p <> 0L))
    |> Seq2.do2 (fun (primes, i, _) -> primes.Add(i))
    |> Seq.map (fun (_, i, _) -> i)
    |> Seq.skipWhile (fun i -> i < minValue)

[<EntryPoint>]
let main argv = 
    let stopwatch = Stopwatch.StartNew()
    let result = (1000000000000L, 1000000001000L) ||> getPrimeNumbers |> Seq.toArray
    stopwatch.Stop()

    result |> Seq.iter (printfn "%A")
    stopwatch.Elapsed.TotalSeconds |> printfn "%A seconds"
    0


 

プログラムを実行します。

実行結果

結果は、C# よりも遅くなりました。
F# は構文糖衣が多く、コンパイル時にクラスに置き換わるものがあるため、
実行時に生成されるオブジェクトが多くなるのが原因であると予想されます。

 

作成したサンプル
PrimeNumbersConsoleF (GitHub)

バージョン情報
.NET Framework 4.5

参照
エラトステネスの篩 – Wikipedia
シーケンス (F#) (MSDN)
LINQ で素数を求める (C#)

カテゴリー: プログラミング言語. タグ: , . 1 Comment »

もし C# で形式的検証ができたら

C# では、コンパイル時に静的にコードをチェックし、警告やエラーを通知してくれます。
例えば、次のようなものです。

到達できないコード

ジェネリック型制約

1 つ目の例はステートメントの条件分岐により、そのスコープに到達できるかどうかを判定しています。
実行はでき、致命的ではないため、エラーではなく警告が通知されています。
2 つ目の例の where 句では、ジェネリック型に対する制約が指定されています。

現時点のコンパイラもそれなりに強力な判断能力を持っているとは思いますが、
もし C# のコンパイラがさらに空気を読んで賢くなったら、
どのようなプログラミング エクスペリエンスを実現できるのかを考えてみましょう。

実装のお題として「与えられた 2 つの整数を昇順に並べ替えるメソッド」という単純なものを設定し、
どうすればバグのないプログラミングができるかを考えます。

まず、並べ替えのメソッドが満たすべき条件は次の通りです。

  1. 実行結果が意図した順番に並んでいる
  2. 実行前の値のセットと実行後の値のセットが同じである

そこで、メソッドの実装を始める前に、メソッドのシグネチャでこれらの条件を表現してみます。

Program.cs


/*
* このプログラムには、架空の機能が含まれます。
*/
class Program
{
    static void Main(string[] args)
    {
        var sorted = Sort(new TwoValues(2, 1));
    }

    // (架空の機能) 引数に対する高度な制約。
    static OrderedTwoValues Sort(TwoValues v) where Sort(v).SetEquals(v)
    {
        // TODO: あとで実装。
        throw new NotImplementedException();
    }
}

// (架空の機能) null を代入できない型。
public class TwoValues where this != null
{
    public int X { get; private set; }
    public int Y { get; private set; }

    public TwoValues(int x, int y)
    {
        X = x;
        Y = y;
    }

    public bool SetEquals(TwoValues v)
    {
        return X == v.X ? Y == v.Y
            : X == v.Y && Y == v.X;
    }
}

public class OrderedTwoValues : TwoValues
{
    // (架空の機能) 引数に対する高度な制約。
    public OrderedTwoValues(int x, int y)
        : base(x, y) where x <= y
    {
    }
}


 

int[] や List<int> の代わりに、TwoValues クラスを定義して 2 つの整数を表現しています。
また、TwoValues クラスを継承して、順序を保持する OrderedTwoValues クラスを定義します。
このコンストラクターにある「where x <= y」は、
静的チェックのレベルで引数が x <= y を満たした状態でコンストラクターを呼び出さなければ、
コンパイルがエラーとなることを意味することにします。

そして、並べ替えを表す Sort メソッドの引数を TwoValues 型、戻り値を OrderedTwoValues 型とします。
これにより、条件 1 が保証されます。

さらに、Sort メソッドに対する制約として「where Sort(v).SetEquals(v)」を追加します。
SetEquals メソッドは ISet<T>.SetEquals メソッドと同様、集合として等しいかどうかを判定します。
これにより、条件 2 が保証されます。

このように強力な制約を導入することで、メソッドのシグネチャだけで条件 1, 2 を表現できました。
ということは、コンパイルが成功するように実装するだけで、このメソッドにはバグが存在しないことが保証されます。
(上記の時点の実装では NotImplementedException が発生するため、条件 2 を満たさず、コンパイルはエラーとなります。)

では、いよいよ Sort メソッドの実装です。


static OrderedTwoValues Sort(TwoValues v) where Sort(v).SetEquals(v)
{
    // コンパイルが成功するための実装。
    return v.X <= v.Y
        ? new OrderedTwoValues(v.X, v.Y)
        : new OrderedTwoValues(v.Y, v.X);
}

 

new OrderedTwoValues(v.X, v.Y) の部分は v.X <= v.Y を満たすスコープの中にいるため、
OrderedTwoValues コンストラクターの制約 x <= y を満たすはずです。
また、new OrderedTwoValues(v.Y, v.X) の部分は v.Y < v.X を満たすスコープの中にいるため、この制約を満たすはずです。

人間が数学の証明をするとき、具体的な数値を代入しなくても、変数のまま大小関係を判定します。
もしコンパイラがもう少し賢くなれば、この程度の判断は十分可能でしょう。

同様に、OrderedTwoValues コンストラクターの引数には、一方に v.X を、他方に v.Y を渡しているため、
Sort(v).SetEquals(v) を満たします。
ここで例えば return new OrderedTwoValues(0, 1) などと実装してしまうと、コンパイル エラーとなります。

というわけで、上記の実装によりコンパイルは成功し、同時に正しい実装であることが保証されます。
このような手法は形式的検証 (formal verification) と呼ばれ、バグが存在してはならないソフトウェアを作成するときなどに利用されます。
C# においても、そのうち Roslyn をベースとして形式的検証のできるコンパイラが登場するのではないでしょうか。

 

作成したサンプル
SortConsole (GitHub)
MathConsole (GitHub)

参照
形式的検証 – Wikipedia
プログラミング Coq
証明駆動開発入門

カリー化の LINQ への応用 (C#)

カリー化の実用について考えてみたいと思います。

まずは、C# でカリー化を表す関数を、拡張メソッドを使って以下のように実装していきます。
カリー化のほか、非カリー化および部分適用のための関数も実装しておきます。
引数の数ごとにメソッドを定義しなければなりませんが、ここではとりあえず T3 までにしておきます。


public static class FunctionHelper
{
    // カリー化
    public static Func<T1, Func<T2, TResult>> Curry<T1, T2, TResult>(this Func<T1, T2, TResult> func)
    {
        return p1 => p2 => func(p1, p2);
    }

    public static Func<T1, Func<T2, T3, TResult>> Curry<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func)
    {
        return p1 => (p2, p3) => func(p1, p2, p3);
    }

    // 非カリー化
    public static Func<T1, T2, TResult> Uncurry<T1, T2, TResult>(this Func<T1, Func<T2, TResult>> func)
    {
        return (p1, p2) => func(p1)(p2);
    }

    public static Func<T1, T2, T3, TResult> Uncurry<T1, T2, T3, TResult>(this Func<T1, Func<T2, T3, TResult>> func)
    {
        return (p1, p2, p3) => func(p1)(p2, p3);
    }

    // 部分適用
    public static Func<T2, TResult> Partial<T1, T2, TResult>(this Func<T1, T2, TResult> func, T1 arg1)
    {
        return func.Curry()(arg1);
    }

    public static Func<T2, T3, TResult> Partial<T1, T2, T3, TResult>(this Func<T1, T2, T3, TResult> func, T1 arg1)
    {
        return func.Curry()(arg1);
    }
}


 

さて、次のようなコレクション操作をしたいと思います。

  • 奇数の二乗を先頭から 10 個取得する
  • 処理結果は文字列として比較したときの順序で並べる
  • 処理結果は整数の配列型とする

期待結果は [1, 121, 169, 225, 25, 289, 361, 49, 81, 9] という配列ですが、LINQ to Objects で次のように書けます。


static void Main()
{
    var result = Enumerable.Range(1, int.MaxValue)
        .Where(i => i % 2 == 1)
        .Select(i => i * i)
        .Take(10)
        .OrderBy(Convert.ToString)
        .ToArray();
}


 

もしこの他に、「偶数」「3 で割り切れる」のようなロジックをどこかで実装しなければならないとしたらどうでしょう。

今回はラムダ式で書けてしまう程度の単純な例なのであまり利点が感じられないようにも見えますが、
関数自体をパラメーター化することで関心事を分離できます。
つまり、関数の本質に相当する部分 (上の例では、「余りが等しい」のみを表す部分) をグローバルに用意しておき、
パラメーターを与えることで具体的に必要な関数を作成する方法が考えられます。

部分適用関数 (Partial メソッド) を利用すれば、次のように実装できます。


/// <summary>指定された剰余を持つかどうかを判定します。</summary>
static readonly Func<int, int, int, bool> Mod = (remainder, divider, value) => value % divider == remainder;
/// <summary>累乗を求めます。</summary>
static readonly Func<int, int, int> Power = (index, value) => (int)Math.Pow(value, index);

static void Main()
{
    var result = Enumerable.Range(1, int.MaxValue)
        .Where(Mod.Partial(1).Partial(2))
        .Select(Power.Partial(2))
        .Take(10)
        .OrderBy(Convert.ToString)
        .ToArray();
}


このように、LINQ to Objects のメソッドの引数に渡す関数を作成する手段として、カリー化を応用できます。

バージョン情報
C# 3.0 以降
.NET Framework 3.5 以降

参照
カリー化 – Wikipedia
C#でカリー化
C#でカリー化と部分適用

switch における変数の宣言 (Objective-C)

Objective-C では、switch ステートメントのセクションの最初の行で変数を宣言するとビルド エラーになるようです。

1-1

これは変数が int 型の場合ですが、解決方法を 2 つ見つけました。

まずは、case ラベルの直後にセミコロン (;) を書くというものです。
これのおかげで 2 行目ということになるのでしょう。

1-2

もう 1 つは、セクションを波かっこ ({ }) で囲むというものです。
スコープが明示されるということでしょう。

1-3

では次に、変数が NSString 型の場合はどうでしょうか。

この場合はなんと、セミコロンを使う方法が通用しません。
セクション内の何行目に記述してもエラーとなるようです。
(もっと複雑なコードを記述したときに、NSString 型でエラーにならないこともあるのですが、条件がわかりません。)

2-1, 2-2

波かっこを使う方法で解決します。

2-3

さらに、default セクション内で NSString 型の変数を試してみました。
この場合は、セミコロンを使う方法でも波かっこを使う方法でも解決できるようです。

3-1, 3-2, 3-3

ちなみに C# では、上記の場合にはエラーにはなりませんが、
複数のセクションで同じ名前の変数を宣言する場合、それぞれのセクションを波かっこで囲まなければなりません。

4-1

4-2

バージョン情報
Xcode 4.3.3