foldとreduceとsum

# はじめに
いわゆる「畳み込み」処理を行うための[高階関数](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96%A2%E6%95%B0)が、いろいろなプログラミング言語で用意されています。

それぞれの言語では、`fold`、`reduce`のいずれかの関数名であることが多いようです。
しかし、D言語では`fold`と`reduce`の両方が用意されています。
なぜそうなのかを調べた際のメモになります。

[参考：いろいろなプログラミング言語の高階関数](https://qiita.com/dico_leque/items/4662a0223cb6bfb19bd3)

さらに、`fold`と`sum`についても調べました。

# foldとreduce
くりかえしになりますが、D言語では「畳み込み」処理を行う関数として、[fold](https://dlang.org/phobos/std_algorithm_iteration.html#.fold)と[reduce](https://dlang.org/phobos/std_algorithm_iteration.html#.reduce)があります。

```d:sample1.d
import std;
void main()
{
    int[] arr = [10, 20, 30, 40];
    writeln(fold!("a + b")(arr));
    writeln(reduce!("a + b")(arr));
}
```
```text:実行結果
100
100
```
`sample1.d`では、配列`arr`に格納された値を足し合わせた結果を表示します。
[fold](https://dlang.org/phobos/std_algorithm_iteration.html#.fold)でも[reduce](https://dlang.org/phobos/std_algorithm_iteration.html#.reduce)でも、同じように使えて、結果も同じ`100`です。

次に、途中まで集計を行った小計`subtotal`があり、小計に配列`arr`を足し合わせる場合を考えます。

```d:sample2.d
import std;
void main()
{
    int subtotal = 50;
    int[] arr = [10, 20, 30, 40];
    writeln(fold!("a + b")(arr, subtotal));
    writeln(reduce!("a + b")(subtotal, arr));
}
```
```text:実行結果
150
150
```
[fold](https://dlang.org/phobos/std_algorithm_iteration.html#.fold)と[reduce](https://dlang.org/phobos/std_algorithm_iteration.html#.reduce)で引数の呼び出し順序が異なります。
実際に、`Phobos`内のソースコード`iteration.d`を調べると、引数の呼び出し順序を変えていることがわかります。

```d:iteration.dから抜粋
auto fold(R, S...)(R r, S seed)
{
    static if (S.length < 2)
    {
        return reduce!fun(seed, r);
    }
    else
    {
        import std.typecons : tuple;
        return reduce!fun(tuple(seed), r);
    }
}
```

ソースコードからもわかるように、`reduce`が先に実装されていて、バージョン`2.071`で`fold`が追加されています。

[バージョン2.071 リリース情報](https://dlang.org/changelog/2.071.0.html)
> Library Changes
> 8.fold was added as an alternative to reduce with argument order swapped.

UFCSを利用する際に、より適した`fold`を追加したようです。
[参考：Forumでの議論](https://forum.dlang.org/post/n8fkn1$2u7a$1@digitalmars.com)

以下に、UFCSを使って記述しました。
`fold`の方が、`arr`に対しての「畳み込み」処理であることが直感的にわかるかと思います。

```d:sample3.d
import std;
void main()
{
    int subtotal = 50;
    int[] arr = [10, 20, 30, 40];
    writeln(arr.fold!("a + b")(subtotal));
    writeln(subtotal.reduce!("a + b")(arr));
}
```

# foldとsum
バージョン2.071以降であれば、[fold](https://dlang.org/phobos/std_algorithm_iteration.html#.fold)と[reduce](https://dlang.org/phobos/std_algorithm_iteration.html#.reduce)のうち、基本`fold`を使えばよいことがわかりました。
ところで、D言語では配列(や`Range`)を合計するための関数として、[sum](https://dlang.org/phobos/std_algorithm_iteration.html#.sum)も用意されています。
こちらは、`fold!("a + b")`と同じかというと、少し違います。

以下は、`fold`と`sum`のどちらを使っても同じ結果になる例です。

```d:sample4.d
import std;
void main()
{
    int[] arr = [10, 20, 30, 40];
    writeln(arr.fold!("a + b"));
    writeln(arr.sum);
}
```
```text:実行結果
100
100
```

次に、結果が異なる例です。`sum`を使った方は正確な値が得られています。
**浮動小数を単純に加算すると誤差が発生する例です。D言語のバグではなく、他のプログラミング言語でも同じように誤差が発生する点に、ご注意ください。**

```d:sample5.d
import std;
void main()
{
    float[] arr = [ 10000.0, 3.14159, 2.71828];
    writefln("%.5f", arr.fold!("a + b"));
    writefln("%.5f", arr.sum);
}
```
```text:実行結果
10005.86035
10005.85987
```

D言語の`sum`は、浮動小数を扱う場合に、[カハンの加算アルゴリズム](https://ja.wikipedia.org/wiki/カハンの加算アルゴリズム)を使って、誤差が少なくなるように実装されています。
整数を扱う場合は、`fold`と`sum`は同じ動きとなります。

```d:iteration.dから抜粋
auto sum(R, E)(R r, E seed)
if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)))
{
    static if (isFloatingPoint!E)
    {
        static if (hasLength!R && hasSlicing!R)
        {
            if (r.empty) return seed;
            return seed + sumPairwise!E(r);
        }
        else
            return sumKahan!E(seed, r);
    }
    else
    {
        return reduce!"a + b"(seed, r);
    }
}

private auto sumKahan(Result, R)(Result result, R r)
{
    static assert(isFloatingPoint!Result && isMutable!Result, "The type of"
        ~ " Result must be a mutable floating point, not "
        ~ Result.stringof);
    Result c = 0;
    for (; !r.empty; r.popFront())
    {
        immutable y = r.front - c;
        immutable t = result + y;
        c = (t - result) - y;
        result = t;
    }
    return result;
}
```

※追記：コメントいただいた件について、`fold`と`sum`の速度比較を行いました。

`sample4.d`では、要素数1億のdouble型配列を生成して加算を行っています。

```d:sample4.d
static import std.datetime.stopwatch;
import std;
void main()
{
	immutable times = 100_000_000;
	auto rnd = Random();
	double[] arr = generate!(() => uniform01(rnd)).takeExactly(times).array;
	double res1,res2;
	void f1() { res1 = arr.fold!("a + b"); }
	void f2() { res2 = arr.sum; }
	auto r = std.datetime.stopwatch.benchmark!(f1, f2)(1);
	writefln("fold -> %.6f", res1);
	writefln("sum  -> %.6f", res2);
	writefln("fold -> %.6f", cast(double)r[0].total!"usecs" / 1_000_000);
	writefln("sum  -> %.6f", cast(double)r[1].total!"usecs" / 1_000_000);
}
```

```text:コンパイル、実行結果
D:\Dev> ldc2 -release -O sample4.d

D:\Dev> sample4
fold -> 49999807.977276
sum  -> 49999807.977278
fold -> 0.097922
sum  -> 0.056561
```

私の事前予想では、`fold`の方が速いと思っていましたが、`sum`の方が速かったです。
浮動小数の場合、`sum`を使えばよさそうです。

速度比較ということで、`ldc2`でコンパイルしました。
ただし、`dmd`でも`sum`の方が速いという結論は同じでした。

念のため、整数型でも試しましたが、`fold`と`sum`でどちらが速いということはありませんでした。

ということで、足し算の場合は、`sum`を使えばよいが私の結論です。

# おまけの参考情報
[pythonの参考情報](https://www.nslabs.jp/python-higher-order-functions.rhtml)
[Kotlinの参考情報](https://qiita.com/opengl-8080/items/36351dca891b6d9c9687)
[Scalaの参考情報](https://www.scala-lang.org/api/current/scala/collection/Seq.html)
[F#の参考情報](https://docs.microsoft.com/ja-jp/dotnet/fsharp/language-reference/lists)