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つの記法で書きます。

LINQの記法

// クエリ記法
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のコードを以下に。

LINQ_to_Rangeの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さんです。一足早いですが誕生日おめでとうございます！