書式

で用い、「2 変数関数」を「リスト」に木構造的に適用する。

(%i1) tree_reduce(f, [1,2,3,4]);

(%o1)                    f(f(1, 2), f(3, 4))


(%i2) tree_reduce(f, [1,2,3,4,5]);

(%o2)                 f(f(f(1, 2), f(3, 4)), 5)


(%i3) tree_reduce(f, [1,2,3,4,5,6]);

(%o3)              f(f(f(1, 2), f(3, 4)), f(5, 6))

例１　2 数の最大公約数を求める関数 gcd を使って、複数の整数の最大公約数を求める。

(%i4) f(x, y) := gcd(x, y);

(%o4)                   f(x, y) := gcd(x, y)


(%i5) tree_reduce(f, [2,4,6,8,10,12]);

(%o5)                             2

なお、Maxima には、複数整数の最大公約数を求める関数 ezgcd が組み込まれている。

例２　200 個の 2 次式 a*x^2 + b*x + c を かけ算する。for ループで素朴に計算する場合とで、実行時間を比較してみる。まず、200 個の 2 次式をランダムに発生させる。

(%i6) l: makelist(random(1000) * x^2 + random(1000) * x + random(1000), i, 1, 200)$


(%i7) showtime:true;

(%o7)                           true

素朴な方法の場合：

(%i8) s: 1$ for i: 1 thru length(l) do s: expand(s * l[i])$

Evaluation took 0.00 seconds (0.00 elapsed)
Evaluation took 4.58 seconds (4.58 elapsed)

tree_reduce を使った場合：

(%i9) f(x, y) := expand(x * y);

(%o9)                  f(x, y) := expand(x y)


(%i10) tree_reduce(f, l)$

Evaluation took 0.72 seconds (0.72 elapsed)

tree_reduce を使う方が 6 倍ぐらい速い。