Divide & Conquer divides, but doesn't conquer

[Paul Backus]

On Monday, 25 May 2020 at 15:59:57 UTC, Andrei Alexandrescu wrote:
> On 5/25/20 1:59 AM, FeepingCreature wrote:
>> To add to the good previous points: the divide-and-conquer 
>> strategy can take advantage of caching for the leaf 
>> instantiations with one parameter. That is, 8 template 
>> instantiations can trivially be reused, and the others can 
>> sometimes be reused if they hit a common subtree. The linear 
>> instantiation can only be reused once or twice at the very end.
>
> Not sure I understand. A,...,H are assumed to be distinct. The 
> number of templates generated is the same regardless of 
> memoization.

I think the idea is that you can potentially re-use template 
instances across separate calls to staticMap. So for example, if 
you have `staticMap!(A, B, C, D)` and `staticMap!(A, B, E, F)`, 
you get:

staticMap!(pred, A, B, C, D)
staticMap!(pred, A, B)
staticMap!(pred, A)
staticMap!(pred, B)
staticMap!(pred, C, D)
staticMap!(pred, C)
staticMap!(pred, D)

staticMap!(pred, A, B, E, F)
staticMap!(pred, E, F)
staticMap!(pred, E)
staticMap!(pred, F)