 # Reduce String concat combinator tree shapes by folding constants into prependers

XMLWordPrintable

#### Details

• Type: Enhancement
• Status: Resolved
• Priority: P4
• Resolution: Fixed
• Affects Version/s: None
• Fix Version/s:
• Component/s:
• Labels:
• Subcomponent:
• Resolved In Build:
b19

#### Description

Consider a program enumerating all ways of concatenating a mix of constants with 3 String arguments:

String s = ...;
String concat;

// no constant
concat = s + s + s;

// 1 constant
concat = "c" + s + s + s;
concat = s + "c" + s + s;
concat = s + s + "c" + s;
concat = s + s + s + "c";

// 2 constants
concat = "c" + s + "c" + s;
concat = "c" + s + s + "c" + s;
concat = "c" + s + s + s + "c";
concat = s + "c" + s + "c" + s;
concat = s + "c" + s + s + "c";
concat = s + s + "c" + s + "c";

// 3 constants
concat = "c" + s + "c" + s + "c" + s;
concat = "c" + s + "c" + s + s + "c";
concat = "c" + s + s + "c" + s + "c";
concat = s + "c" + s + "c" + s + "c";

// 4 constants
concat = "c" + s + "c" + s + "c" + s + "c";

total variants: 1 + 4 + 6 + 4 + 1 = 16 => sum of binomial coefficients of 4 choose n for n = 0...4, which is 2 ^ 4. For four arguments, we'd get sum n = 0...5 of 5 choose n = 32 variants; five arguments = 64...

So effectively there are 2^(n+1) shape variants for n Object arguments mixed with 0 to n+1 constants.

With a patch to fold constant + argument into a single prepender MH, binding the constant to an instance of such a prepender, we on one hand double the number of prepender variants we can generate (from max 7 to max 14), but the stem of the MH combinator tree becomes perfectly shareable between most of the above expressions, effectively turning an O(2^n) expansion factor into a constant factor (2 most likely: we get one shape for when there's a trailing constant, another when there's not).

For the above simple program alone we load and generate 113 fewer classes (705 -> 592)

#### People

Assignee: Claes Redestad
Reporter: Claes Redestad