drangesというライブラリのお話の第一回目。
dranges.algorithmについて。
drangesはD言語の標準ライブラリstd.rangeとかstd.algorithmを強化しようという理由で生まれたみたいです。
drangesを使うための前準備
drangesを拾ってきます。
現在は私が勝手にコードを保守してます。
dranges
前はだれも保守してなかったようで、2年前のソースコードが大半でした(笑)
dranges.algorithm.tmap
tmapはtuple mapの略でしょう。
tmapは入力として、複数のレンジか、単一のレンジを受け取ります。
複数のレンジを受け取ったとき
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,...が割り当てられます。
単一のレンジを受け取ったとき
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です。
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の直前項のみに依存する場合と同じ動作です。
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です。
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)によって新たなレンジを作り、それらを結合したレンジを返します。
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していきます。
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の右からバージョンです。
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
漸化式からレンジを作ります。
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は停止条件も渡すので前進レンジになります。
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"に対応します