D言語 Advent Calendar 2012の21日目の記事です。
D言語のRangeの事を軽くと、D言語でLINQをどう実現するかというお話をします。
Rangeって？
RangeというのはD言語で扱われるコレクションのこと。
コレクションの例としては、ListとかMapとかQueueとかあります。
D言語の場合、クラスや構造体に特定のメソッド・メンバを実装すればOKです。
Rangeには幾つかの種類があって、下の表の通りです。
| Rangeの種類 | 説明 |
|---|---|
| InputRange | empty、front、popFrontが実装されてる |
| OutputRange | putが実装されてる |
| ForwardRange | InputRange+saveが実装されてる |
| BidirectionalRange | ForwardRange+back、popBackが実装されてる |
| RandomAccessRange | BidirectionalRange+length、opIndexが実装されている |
最低でもInputRangeとして実装されていればforeachで回す事ができます。
また、std.rangeをincludeすればisXXXXRangeでコンパイル時に各種Rangeの条件を満たしてるかコンパイル時に判別してくれます。
他にも色々判別出来て、isInfinitで無限リストかどうかとか、hasSlicingでスライシング（range[3..5]みたいなの)が提供されているか判別してくれます。もちろん、全部コンパイル時に！
LINQって？
LINQっていうのはLanguage INtegrated Query(統合言語クエリ)の略です。
.NET Framework3.5から提供された機能の事で、C#やVisual Basicで色んなデータ構造に対して同じクエリでデータの操作を可能にしようっていう奴です。
扱うデータも、IEnumerable・IEnumerable<T>コレクションを扱うLINQ to Objects、XMLを扱うLINQ to XML、RDBを扱うLINQ to SQLやLINQ to Entities等々色々あります。
変わり種として非同期やイベントの操作を行うReactive Extensionsなんてなんてものもあったり。
LINQってO/Rマッパーなのでは、とか言われるのですがO/RマッパーなはあくまでLINQのほんの一部なのです。
では、そのLINQの特徴を以下に軽く。
2つの記述方法
LINQにはクエリ記法とメソッドチェイン記法があります。
以下に1〜100の中から偶数の数字の二乗の値を取り出す操作を2つの記法で書きます。
// クエリ記法
var query = from x in Enumerable.Range(1, 100)
where x % 2 == 0
select x * x;
// メソッドチェイン記法
var methodChain = Enumerable.Range(1, 100).Where(x => x % 2 == 0).Select(x => x * x);
統一的な操作
LINQ to ObjectsやLINQ to XML、LINQ to SQLやLINQ to Entities等など、扱うデータの種類は色々あります。
だけど、Whereだと記載した条件のものだけ取り出すし、Selectだとコレクションの要素から好きな形式に整形して出力するし、Countだと要素の数を数えるし、OrderByならソートするし、GroupByなら特定の要素でグループ分けしてくれます。
扱うデータが変われど、LINQで目的のデータを扱うやり方が統一されることで、覚えることが少なくて済むし、いちいちリファレンス調べなくてよくなります。
遅延評価
LINQは、LINQで記載したデータに対しその要素にアクセスしようとしない限りデータへの操作を行わない様に実装されています。
上記の記載例だと、queryやmethodChainの箇所ではまだ偶数の判別やxの二乗計算は行われてません。
queryやmethodChainの最初の要素にアクセスしたり、 foreachで各要素を取得したりした時に、初めて判別や計算が実行されます。
RangeでLINQしよう！
先ほど挙げた通り、コレクションに関してはRangeがあります。
クエリ記法は流石にコンパイラ自体のサポートがいるので無理ですが、メソッドチェイン記法ならば2.059で使えるようになったUFCSで可能になります。
他にも、D言語にはラムダ式があったりと実装しやすそうなので、LINQ to Rangeをやってみようかなと思ったのです。
というか、JavaScriptでのLINQ実装であるlinq.jsのリファレンスとかコード見ながらD言語に落とし込んだ感じです。
例としてwhereのコードを以下に。
template where(alias pred) if (is(typeof(unaryFun!pred)))
{
auto where(Range)(Range r) if (isInputRange!(Unqual!Range))
{
return WhereRange!(unaryFun!pred, Range)(r);
}
}
private struct WhereRange(alias pred, Range)
{
alias Unqual!Range R;
R _prevSource;
bool _isAccess;
// コンストラクタ
this(R r)
{
_prevSource = r;
_isAccess = false;
}
// empty(空かどうか)の提供
static if (isInfinite!Range)
{
enum bool empty = false;
}
else
{
@property bool empty() { return _prevSource.any!(pred); }
}
// 一番最初の要素に移動(1回目だけ)
private void popFirst()
{
if(!_isAccess)
{
while(!_prevSource.empty && !pred(_prevSource.front))
{
_prevSource.popFront();
}
_isAccess = true;
}
}
// popFront(取り出す要素を前に一つ先に移動)の提供
void popFront()
{
this.popFirst();
do
{
_prevSource.popFront();
}while(!_prevSource.empty && !pred(_prevSource.front));
}
// front(要素の取得)の提供
@property auto ref front()
{
this.popFirst();
return _prevSource.front;
}
// whereの連打を提供
public auto where(alias newPred)()
if (is(typeof(unaryFun!newPred)))
{
return WhereRange!(delegate bool(typeof(_prevSource.front) x) { return unaryFun!newPred(x) && pred(x);}, Range)(_prevSource);
}
}
std.algorithmを見たりしながら実装しました。
std.algorithmのfilterとほぼ同じ機能なのですが、あっちはfilter用の構造体を作成する際にpredの判定とか実行するので、それも遅延させてみました。
あと、WhereRangeにwhereメソッドがあるのを見て分かる通り、whereにwhereを繋げても、それぞれのpredの論理積の式からWhereRangeを作るので、whereを何回も繋げる、みたいなよくやる書き方をしてもパフォーマンスに影響がありません。
これもlinq.jsや元々のLINQで同じ様になっています。
その他にこんなのを実装してみました。
| 実装した機能 | 説明 |
|---|---|
| any!(pred,Range)(Range r) | Rangeに要素があるかどうか判定する。predを書けばその条件を満たす要素があるか分かる。 |
| count!(Range)(Range r) | Rnageにいくつ要素があるか数える。 |
| skip!(Range)(Range r, size_t count) | Rangeの要素の頭count個を飛ばしたRangeを取得する。 |
| chois!(Range)(Range r) | Rangeの中からランダムで要素を取り出す。 |
| selectMany!(pred, Range)(Range r) | Rangeの各要素を一つのRangeに射影して平坦化する。 |
selectManyについてはよく分からないと思います。図解 SelectManyが図が載ってて分かりやすいので、こちらを見ていただければいいかなと。
LINQにはまだまだいろんな操作があって、linq.jsのリファレンスページのように色々あります。
.Net Framework側のLIQN to Objectsの一覧は「LINQの拡張メソッド一覧と、ほぼ全部のサンプルを作ってみました。(地平線に行く)」が分かりやすいです。
私、気になります！
では最後に、千反田えるを上記のLINQ to Rangeとstd.rangeとstd.algorithmを使って求めてみます。
import std.stdio;
import std.algorithm;
import std.range;
import linq; //LINQ to Rangeを実装してるモジュール
void main()
{
0.iota(1000).map!(n => (a => a[3].repeat.selectMany!"a".skip(n+1).front ~ a[2].repeat.selectMany!"a".skip(n+1).front ~ a[1].repeat.selectMany!"a".skip(n+1).front ~ a[0].repeat.selectMany!"a".skip(n+1).front ~ "反田" ~ ["えー","びー","しー","でぃー","いー","えふ","じー","えいち","あい","じぇー","けー","える","えむ","えぬ","おー","ぴー","きゅー","あーる","えす","てぃー","ゆー","ぶい","だぶる","えっくす","わい","ぜっと"].cycle.skip(n).front)(["", "十", "百","千"].map!(x => ["", "一", "二", "三", "四", "五", "六", "七", "八", "九"].map!(y => ((x!="" && y=="一")? "" : y) ~ ((x!="" && y=="")? "" : x))).map!(x => x.map!(y => y.repeat.take(10 ^^ ["一", "十", "百","千"].countUntil(x.skip(1).front))).selectMany!(x => x)))).skip(1000-1).front.writeln; // 千反田える
}
中途半端極まりねぇぇぇええええええ！ (遅延とか諸々)
selectとかrepeatとかcylceとかzip(2つの配列を同時に回しながらselectする操作)とか実装する時間がなかった……orz。
std.rangeとstd.algorithmを使ってるのは、元からあるmapやrepoeatやcycleである程度は代用出来るので、それを使ってなんとか作りました。
特にzipがあれば1〜1000の数字配列(0.iota(1000)の所)からn反田コレクション(0<n<=1000)を作成しなくてもいいのですが……
なんで俺zip先に実装せんかったんや……
次回予告
というわけで、RangeとLINQに関する説明と、LINQ to Rangeの説明をしました。
LINQ to Rangeだけでなく、D言語でJSONやXMLに対してもLINQ出来たりするとより面白いですね。
次回の22日目は@mono_shooさんです。一足早いですが誕生日おめでとうございます！