:

## Folding Associative Operators

Maple

Maple's foldl and foldr procedures provide a convenient means to generate an n-ary function from a binary operator. For example, from another thread, one can use foldl to create an n-ary and procedure from Maple's binary `and` function:

```myand := proc() foldl(`and`,true,_passed) end proc:
myand(a,b,c);
a and b and c
```

Note that this procedure gives the proper result, true, with no arguments.

If you are interested in how foldl accomplishes this, you can readily inspect its code, since it is not a builtin function:

```interfacelevel(verboseproc=2):
print(foldl);

proc(rator, id)
local accum, i;
accum := id;
for i from 3 to nargs do accum := rator(eval(accum, 1), args[i])
end do;
eval(accum, 1)
end proc
```

I do not understand the purpose of the eval( . , 1).  For the few cases I tested, it is slightly faster without that.  Is that a leftover from when evaluation within Maple procedures was not just one level?  Was that ever the case?  It is also slightly faster to directly access the arguments in the loop rather than using an index:

```myfoldl2 := proc(f,id)
local accum, x;
accum := id;
for x in _rest do
accum := f(accum, x);
end do;
accum;
end proc:
```

An interesting aspect of the particular example, folding with the `and` function, is that the boolean and operator is associative. However, this associativity is not reflected in the generated structure.  That is, if you dismantle the output you will see that it is equivalent to `and`(`and`(`and`(a,b),c),d).

While there is, ultimately, little we can do about the left-associativity of Maple's and-operator, we can construct a different, but logically equivalent, expression that may evaluate faster.  The present construction is a heavily unbalanced tree.  If we substituted the value a = false into the expression, Maple would have to evaluate all three and operations to determine that the result was false.  If we had used foldr, then it would only have to evaluate one operation, however, the tree would be equally unbalanced, just in the other direction.

Can we generate a balanced tree? Here is one approach.

```foldassoc := proc(f,id)
local i;
if _npassed > 3 then
procname(f, seq(f(_passed[i..i+1]), i=2.._npassed-1, 2)
, `if`(_npassed :: 'odd'
, NULL
, _passed[-1]
));
elif _npassed = 3 then
f(id, _rest);
else
id;
end if;
end proc:
```

While it looks rather complicated, and is a recursive procedure, we find that when called with the `and` operator it is almost as fast as foldl.  The result, however, is a reasonably balanced expression that can evaluate significantly faster upon subsitition of actual values.  This procedure can also be better than foldl for extending some binary operations.  I originally devised it to speed up lcm, which uses foldl.

﻿