[サンプル] クエリ式とリスト内包

2007/09/29 (Last updated:2007/10/06)

キーワード

リスト内包

概要

C# 3.0 の「LINQ」を使うと、リスト内包（list comprehensions）のようなことが可能。

内包と外延

ここでいう内包ってのは、元々は公理的集合論の用語で、

内包（intension）記法： {f(x) | x ∈ A} みたいな書き方。
外延（extension）記法： {a, b, c, d, e, …} みたいな書き方。

というようなものの事をいいます。この言葉はさらにさかのぼると、哲学とか論理学の用語で、

内包：「ある事物が充たすべき条件」… 事物が内に持っているだろう性質。
外延：「ある条件を充たす事物の集合」… 具体例で外堀埋めるように事物を記述。

というような意味です。要するに例えば、犬というものを定義するに当たって、

内包：犬は、哺乳類で、4足歩行で、群れを成す生き物で、・・・
外延：お隣のポチは犬、向かいのシロも犬・・・

というような考え方の区分。こういう考え方を集合論の記号で表したものが最初に例示したような内包記法・外延記法です。

内包記法：犬＝ {x | x ⊂ 哺乳類, x は4足歩行, x は群れを成す, ・・・}
外延記法：犬＝ {お隣のポチ, 向かいのシロ, ・・・}

リストの初期化

具体例を挙げてみましょう。 0 以上 10未満の偶数の集合といわれると、数学的には以下の2通りの書き方ができます。

外延記法： { 0, 2, 4, 6, 8 }
内包記法： { n | n ∈10, 2|n } あるいは { 2n | n ∈5 }

ただし、集合論的には 10 ってのは { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } という集合と同じ意味で、 2|n は「2 は n の約数」（したがって、n は偶数）の意味です。

で、プログラミング言語的には、外延記法の方は、C 言語の配列でもできます。

int evens[] = { 0, 2, 4, 6, 8 };

でも、内包記号の方は無理です。これと近いことを C 言語でやろうとすると、以下のようになります。

int evens[5];
int i = 0;
for (int k = 0; k < 10; ++k)
{
  if (k % 2 == 0)
  {
    evens[i] = k;
    ++i;
  }
}

C# の List を使って書くとほんの少しだけ数学の記法に近づく事ができて、以下のようになります。

var _10 = Enumerable.Range(0, 10);

List<int> evens = new List<int>();
foreach (var n in _10)
  if (n % 2 == 0)
    evens.Add(n);

とはいえ、 n ∈10 の部分を n in _10 と書けたくらいで、数学の集合の内包記法とは程遠いです。 {} の中に条件式を書けるわけじゃないですし、何よりも、「先にリストを作ってからそれに値を Add する形で初期化する」って形になるのが少々不恰好。

リスト内包

いくつかの言語では、数学の内包記法に似た書き方でリストを初期化できる構文を持っています。この構文をリスト内包（list comprehensions）と呼びます。（intension と comprehension はほぼ同義語。日本語訳的にはどっちも内包。）

特に、関数型言語にそういう機能を持った言語が多いんですが、例えば、Erlang では以下のようにしてリストを作れます。

Ten = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Evens = [n || n <- Ten, n rem 2 == 0]

関数型言語でも F# の場合、以下のように for とか when が必要。

let evens = { for n in 0 .. 9 when n % 2= 0 -> n }

関数型言語以外でも、例えば、Python はリスト内包構文を持っています。 F# と同様、数学の集合の内包記法とは違って、for とか if とかいうキーワードが必要になります。

ten = range(0, 10)
evens = [n for n in ten if n % 2 == 0]

これは、以下のように解釈されるようです。（Python にはそんなに詳しくないんで、もしかすると間違ってるかも。）

ten = range(0, 10)
evens = []
for n in ten :
  if n % 2 == 0 :
    evens.append(n)

これは、前節の最後で書いたような C# のコードに近いです。

クエリ式とリスト内包

さて、前節の Python コード

ten = range(0, 10)
evens = [n for n in ten if n % 2 == 0]

と、以下の C# コードを比べてみてください。

var ten = Enumerable.Range(0, 10);
var evens = from n in ten where n % 2 == 0 select n;

先頭の n が末尾の select n に、 for が from に、 if が where に変わっていますが、そういう見かけの差を除けばやってることは一緒です。そして、結果として得られるのは同じ「0以上10未満の偶数」になります。

（実際には、Python 版はリスト、C# 版で IEnumerable になるんで、細かいこと言うといろいろ違いますけど。あと、生成されるコードも全然違います。）

ということで、C# 3.0 のクエリ式は、書き方こそ微妙に違えど、性質はリスト内包に近いかも。

まあ、クエリ式の方が、join とか order by とか group by とかが使えて、より高機能なんですが。

具体例： 3次元格子点の平面への投影

リスト内包表記っぽいものを実際に C# 3.0 のクエリ式で書いてみましょう。

題材

ここでの例として、3次元上の格子点を平面に投影してみた結果がどういう点を描くかというのをやってみます。 3次元の格子点って言うと、数学の記号を使って書くと以下のような感じです。

L₃={ (x, y, z)∈R³| x ∈N, y ∈N, z ∈N }

で、3次元上の点を平面に投影する関数 Pr: R³→R² を用意して、以下のような集合を作ります。

P ={ Pr(p)| p ∈ L₃ }

簡単化のため、投影面は原点を通る平面に限定します。で、この平面の正規直交基底を i₁, i₂ とすると、投影関数 Pr は以下のように書くことができます。

Pr(p)=( p ⋅i₁ , p ⋅i₂ )

すなわち、投影された点の集合 P は以下のように書けます。

P ={ ( p ⋅i₁ , p ⋅i₂ )| p ∈ L₃ }

コーディング

まず、3次元上の格子点は C# 3.0 的に書くと以下のような感じ。

var points3d =
  from x in Enumerable.Range(-N, 2 * N)
  from y in Enumerable.Range(-N, 2 * N)
  from z in Enumerable.Range(-N, 2 * N)
  select new Vector3D(x, y, z);

N は適当な定数です。無限個の点を扱うわけにもいかないので、N で探索範囲を限定します。 Vector3D は「WPF」の System.Windows.Media.Media3D.Vector3D クラス。 Enumerable は .NET Framework 3.5 で追加された System.Linq.Enumerable クラスです。

平面への投影は、平面の基底ベクトル i1, i2 を与えて、以下のようにします。

var projectedPoints =
  from p in points3d
  let x = Vector3D.DotProduct(p, i1)
  let y = Vector3D.DotProduct(p, i2)
  select new Point(x, y);

そこそこ数学のイメージ通りにコーディングできているんじゃないかと。

ちなみに、（原点を通る）平面は法線ベクトル1つを与えて定められるわけですが、法線ベクトル normal から適当な平面状の基底ベクトル2つを求めるには、以下のような関数を使います。

static void GetOrthogonalBase(
  Vector3D normal, out Vector3D i1, out Vector3D i2)
{
  Vector3D temp;

  if (normal.X > normal.Y)
    if (normal.X > normal.Z) temp = new Vector3D(0, 1, 0);
    else temp = new Vector3D(1, 0, 0);
  else
    if (normal.Y > normal.Z) temp = new Vector3D(0, 0, 1);
    else temp = new Vector3D(1, 0, 0);

  i1 = Vector3D.CrossProduct(normal, temp); i1.Normalize();
  i2 = Vector3D.CrossProduct(normal, i1); i2.Normalize();
}

あと、探索する範囲をもう少し絞って、「平面から遠い点」と「表示可能な範囲外」の点を除外するために、以下のような条件をつけておきます。

var points3d = (
  from x in Enumerable.Range(-M, 2 * M)
  from y in Enumerable.Range(-M, 2 * M)
  from z in Enumerable.Range(-M, 2 * M)
  select new Vector3D(x, y, z) into p
  let distance = Math.Abs(Vector3D.DotProduct(p, normal))
  where distance < THICKNESS
  select p
  ).ToArray();

Vector3D i1, i2;
GetOrthogonalBase(normal, out i1, out i2);

var projectedPoints =
  from p in points3d
  let x = Vector3D.DotProduct(p, i1)
  let y = Vector3D.DotProduct(p, i2)
  where -WIDTH <= x && x <= WIDTH
    && -WIDTH <= y && y <= WIDTH
  select new Point(x, y);