dranges.algorithm

drangesというライブラリのお話の第一回目。
dranges.algorithmについて。
drangesはD言語の標準ライブラリstd.rangeとかstd.algorithmを強化しようという理由で生まれたみたいです。

##drangesを使うための前準備
drangesを拾ってきます。
現在は私が勝手にコードを保守してます。
[dranges](https://github.com/k3kaimu/dranges)
前はだれも保守してなかったようで、2年前のソースコードが大半でした(笑)

##dranges.algorithm.tmap
tmapはtuple mapの略でしょう。
tmapは入力として、複数のレンジか、単一のレンジを受け取ります。

####    複数のレンジを受け取ったとき

```test.d
import std.stdio            : writeln;
import std.range            : iota, repeat;
import dranges.algorithm    : tmap;

pragma(lib, "dranges");

void main()
{
    auto rng0 = iota(10);
    auto rng1 = repeat(2);
    auto rng2 = [3, 2, 1, 0, 2, 3];
    
    tmap!"a+b+c"(rng0, rng1, rng2).writeln();
}
```

結果は
`[5, 5, 5, 5, 8, 10]`
になります。
このように複数のレンジが渡された場合には、それぞれの要素にa, b, c,...が割り当てられます。

####    単一のレンジを受け取ったとき

```test.d
import std.stdio            : writeln;
import std.range            : iota, repeat, zip;
import dranges.algorithm    : tmap;

pragma(lib, "dranges");

void main()
{
    auto rng0 = iota(10);
    auto rng1 = repeat(2);
    auto rng2 = [3, 2, 1, 0, 2, 3];
    
    tmap!"a+b"(zip(rng0, rng1)).writeln();
    tmap!"a+2"(rng0).writeln();
}
```

結果は
`[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11]`
です。
単一のレンジが渡された場合には、要素がTupleであればそのTupleの要素一つ一つにa, b,...が割り当てられますが、Tuple出ない場合にはstd.algorithm.mapが呼ばれます。


##dranges.algorithm.tfilter
tmapのfilterバージョンです。

##dranges.algorithm.nmap
reduceのような面白い動作を行うmapです。

```test.d
import std.stdio            : writeln;
import dranges.algorithm    : nmap;

pragma(lib, "dranges");

void main()
{
    auto rng = [1, 2, 3, 4, 5];
    
    rng.nmap!"a * b"().writeln();
}
```

結果は
`[2, 6, 12, 20]`
となります。
動作は、
1 * 2,
2 * 3,
3 * 4,
4 * 5,
というふうに、前後の要素の演算となります。
たとえば、nmap!"a * b * c"なら前後3要素の積になります。

##dranges.algorithm.nfilter
nmapのfilterバージョンです。

##dranges.algorithm.iterate
std.algorithm.recurrenceの直前項のみに依存する場合と同じ動作です。

```test.d
import std.stdio            : writeln;
import std.range            : take;
import dranges.algorithm    : iterate;

pragma(lib, "dranges");

void main()
{
    iterate!"a * 2"(1).take(10).writeln();
}
```

結果は`[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]`となります。
recurrenceでは[n-1]となるのがうっとおしい場合に楽できます。

##dranges.algorithm.scan
Haskellでお馴染みのscanです。

```test.d
import std.stdio            : writeln;
import std.range            : iota;
import dranges.algorithm    : scan;

pragma(lib, "dranges");

void main()
{
    iota(10).scan!"a+b"().writeln();
}
```

結果は`[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]`となります。


##dranges.algorithm.flatMap
数学っぽい式で書くと
concat{func(a)| a ∈ range}
でしょうか。rangeの各要素aにたいしてfunc(a)によって新たなレンジを作り、それらを結合したレンジを返します。

```test.d
import std.stdio            : writeln;
import std.range            : iota;
import dranges.algorithm    : flatMap;

pragma(lib, "dranges");

void main()
{
    iota(1, 5).flatMap!"std.range.repeat(a, a)"().writeln();
}
```

結果は`[1, 2, 2, 3, 3, 3, 4, 4, 4, 4]`となります。


今日は眠いのでここまで。


#追加

##dranges.algorithm.reduceR
逆側からreduceしていきます。

```test.d
import std.stdio            : writeln;
import std.range            : iota;
import std.functional       : unaryFun;
import dranges.algorithm    : reduceR;

pragma(lib, "dranges");

void main()
{
    /* reduceR!fun(R) = fun(R, reduceR!fun(R.drop(1)))
     * reduceR!fun(seed, R = fun(R, reduceR!fun(seed, R.drop(1))))
     */
    iota(1, 11)
    .unaryFun!(a => reduceR!"a * (b + 2)"(0, a))
    .writeln();
    
    (1*(2*(3*(4*(5*(6*(7*(8*(9*(10*(0 + 2)+2)+2)+2)+2)+2)+2)+2)+2)+2)).writeln();
}
```

結果は

```
8075826
8075826
```

となります。

##dranges.algorithm.scanR
scanの右からバージョンです。

```test.d
import std.stdio            : writeln;
import std.range            : iota;
import dranges.algorithm    : scanR;

pragma(lib, "dranges");

void main()
{
    iota(5)
    .scanR!"a+b"()
    .writeln();
    
    //[4, 4+3, 4+3+2, 4+3+2+1, 4+3+2+1+0]
}
```

結果は

```
[4, 7, 9, 10, 10]
```

##dranges.algorithm.unfold
漸化式からレンジを作ります。

```test.d
import std.range            : take;
import std.stdio            : writeln;
import dranges.algorithm    : unfold;

pragma(lib, "dranges");

void main()
{
    unfold!"tuple(a, b, c, a+b+c)"(0, 0, 1)
    .take(10)
    .writeln();
}
```

結果は

```
[0, 0, 1, 1, 2, 4, 7, 13, 24, 44]
```

recurrenceでいいんじゃないかなあとか思ってしまいますが、まあ…

##dranges.algorithm.unfold2
unfoldが無限レンジを返すのに対して、unfold2は停止条件も渡すので前進レンジになります。

```test.d
import std.stdio            : writeln;
import dranges.algorithm    : unfold2;

pragma(lib, "dranges");

void main()
{
    unfold2!("tuple(a, b, c, a+b+c)", "a > 100")(0, 0, 1)
    .writeln();
}
```

```
[0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81]
```

------
2012年11月22日追記
------

##dranges.algorithm.sumとdranges.algorithm.product
それぞれreduce!"a+b"とreduce!"a*b"に対応します