# Problem with Compile and Flatten

I want to get two lists within a compiled function, where r is an integer:

Insert[
DeleteCases[
Flatten[
Table[{i, j}, {i, 0, r - 1}, {j, i, r - 1}], 1],{0, 0}], {0, r}, r];

Flatten[Table[{i, j}, {i, r - 1}, {j, 0, i - 1}], 1];


But Flatten and Compile don't seem to work very well together:

Compile[{{r, _Integer}},
Module[{list, i = 0, j},
list = Table[{i, j}, {i, 0, r - 1}, {j, i, r - 1}];
Flatten[list, 1];
]
]


This yields Compile::cplist: list should be a tensor of type Integer, Real, or Complex; evaluation will use the uncompiled function.. It works fine without the Flatten though.

It looks like the problem you are running in to is because list is a ragged array, which is not allowed. Replace {j,i,r-1} with {j,r-1} and you get a function that compiles and runs (despite the fact that it doesn't give you the desired output).

One way to get your desired output is to create a regular array with some criterion that can be selected for removal afterwards. Note I specifically avoid the use of pattern since pattern matching is not allowed in Compiled functions.

This seems to work:

f = Compile[{{r, _Integer}},
Module[{list, i = 0, j},
list = Table[{i, If[j < i, -1, j]}, {i, 0, r - 1}, {j, 0, r - 1}];
Select[Flatten[list, 1], #[[2]] =!= -1 &]]]


One obvious solution that comes to my mind, especially when I see your DeleteCases- and Insert-calls, is to use InternalBag. This makes is somewhat easy to collect all elements of your result. Let's start with the compiled equivalent of

Flatten[Table[{i, j}, {i, r - 1}, {j, 0, i - 1}], 1];

Inside a compiled function, you would start by creating a new bag for your result. Important is that I'm storing your two-dimensional tensor into a one-dimensional list. This is not a problem, because we always add a pair e.g. {0,2} so we know that your final result can easily be rebuilt by using Partition[..,2] at the end:

f1 = Compile[{{r, _Integer}},
Module[{res = InternalBag[Most[{0}]]},
Do[InternalStuffBag[res, {i, j}, 1], {i, r - 1}, {j, 0, i - 1}];
Partition[InternalBagPart[res, All], 2]
]
]


Knowing this, makes the creation of your other list easy. Just replace the DeleteCases and Insert calls by appropriate conditional events:

f2 = Compile[{{r, _Integer}},
Module[{res = InternalBag[Most[{0}]], c = 0},
Do[
If[c++ == r, InternalStuffBag[res, {0, r}, 1]];
If[i == 0 && j == 0, Continue[]];
InternalStuffBag[res, {i, j}, 1], {i, 0, r - 1}, {j, i, r - 1}
];
Partition[InternalBagPart[res, All], 2]
]
]


You can use CompilePrint from the <<CompiledFunctionTools package to verify that everything is properly compiled down.

• I would like to know that why use res = InternalBag[Most[{0}]], rather than res = InternalBag[Most[{0}]]. Because Most[{0}] is equvalent to {}.
– xyz
Jun 1, 2015 at 2:47
• +1 for using the terms "one obvious solution" and "Internal Bag" in the same sentence. As far as I can tell, SE is the primary documentation source for the Internal context. Are you aware of others? Jun 1, 2015 at 12:06
• @ShutaoTang Yes, Most[{0}] is equivalent to {}, but with this, Mathematica has the chance to see that I want an integer-list. This is the whole purpose. I'm not aware of any different way to make this kind of type-inference work. If you leave this out, then the created Bag will be of type Real. Jun 1, 2015 at 12:11
• @bobthechemist No, I'm not aware of any official documentation. In the linked Q&A, I gave a reference to a MathGroup message of Daniel Lichtblau. Additionally, there are some threads on SO about it, but no official documentation. Jun 1, 2015 at 12:13

All what you have to do is to tell Compile that list and result are in fact tensors. You can do that by adding the optional arguments at the end of Compile: {list,_Integer,3} meaning that list is an integer tensor of rank 3, and {result, _Integer,2} meaning that result is a tensor of rank 2. list should go out of the module in this case.

Compile should look like:

f1 = Compile[{{r, _Integer}},
result = Module[{i = 0, j},
list = Table[{i, j}, {i, 0, r - 1}, {j, i, r - 1}];
Flatten[list, 1]
]; (* End Module *)
result (* Return result *)
, {{list, _Integer, 3}, {result, _Integer, 2}}
]; (* End Compile *)


which yields:

{{0,0},{0,1},{0,2},{0,3},{0,4},{1,1},{1,2},{1,3},{1,4},{2,2},{2,3},{2,4},{3,3},{3,4},{4,4}}

• The real problem is that the compiled code still calls the main-evaluator basically for the complete body of your function. May 31, 2015 at 23:48
• @halirutan Interesting .. How can I check for that? Jun 1, 2015 at 0:45
• Load the package <<CompiledFunctionTools  and try CompilePrint[f1] on your function. Btw, result and list are not local variables in your compile call which makes it impossible to create a completely self-contained compiled function. Jun 1, 2015 at 1:11
• @halirutan Yes, I am aware of the non-local variables (I didn't really have time to think about how to solve this problem, as they can't be in a module and still be in Compile specs - or at least that's what I tried). Thanks a lot for the introduction to InternalBag`, following its lead opened lots of learning opportunities for me. Thanks again :) Jun 1, 2015 at 3:09