# How to build a list of elements satisfying a certain property without building a list of all elements first?

Is there a way to directly build a list of elements that satisfy a certain property? More precisely, I am looking for a function IncludeIf (this is a placeholder name) that should work like Table but direcly drops all the unwanted elements. E.g.

IncludeIf[i, PrimePowerQ, {i, 1, 1000}]


should create a list of all prime powers among the numbers $\{1,...,1000\}$. The result should be the same as for

Select[Table[i, {i, 1, 1000}], PrimePowerQ]


but without the overhead of first creating a list of maybe far to many elements, and then dropping most of them.

A built-in-function would be preferred, but a work-around is welcome too.

You can use Do together with Reap-Sow:

Reap[Do[If[EvenQ[i], Sow[i]], {i, 100}]][[2, 1]] // Short
(*{2, 4, 6, 8, 10, <<40>>, 92, 94, 96, 98, 100}*)


EDIT

It is interesting to compare the Reap-Sow approach with the linked lists approach.

Reap-Sow approach:

ClearAll[ReapSow];
SetAttributes[ReapSow, HoldAll];
ReapSow[expr_, cond_, spec_] := Reap[
Do[If[cond, Sow[expr]], spec]
][[2, 1]];


ClearAll[LinkedLists];
$temp = f[], Do[ If[cond,$temp = f[$temp, expr]], spec ], List @@ Flatten[$temp]
];


here I intentionally do not introduce local variables not to fool RepeatedTiming by, e.g. Module overhead.

InternalBag cheat:

ClearAll[ReapSowCompiled];
SetAttributes[ReapSowCompiled, HoldAll];
ReapSowCompiled[expr_, cond_, spec_] := Compile[
{},
Module[
{bag = InternalBag[{0}]},
Do[If[cond, InternalStuffBag[bag, expr]], spec];
InternalBagPart[bag, All]
],
CompilationTarget -> "C"
];
cf = ReapSowCompiled[i, EvenQ[i], {i, 10^4}];


Tests in a fresh kernel:

(*A fresh kernel*)
mem1 = MemoryInUse[];
a = ReapSow[i, EvenQ[i], {i, 10^4}]; // RepeatedTiming // First
MemoryInUse[] - mem1
(*0.01*)
(*58992*)

(*A fresh kernel*)
mem1 = MemoryInUse[];
b = LinkedLists[i, EvenQ[i], {i, 10^4}]; // RepeatedTiming // First
MemoryInUse[] - mem1
(*0.01*)
(*410696*)

(*A fresh kernel*)
mem1 = MemoryInUse[];
c = cf[] // Rest; // AbsoluteTiming// First
MemoryInUse[] - mem1
(*0.000326986*)
(*47184*)


So, a complex tree structure of pointers seems to involve a bigger memory overhead then an optimized Reap-Sow or Compiled cheat.

As compiled variant of Sow and Reap, you can use the undocumented InternalBag:

cf = Compile[{{n, _Integer}},
Module[{bag = InternalBag[{0}]},
Do[If[EvenQ[i], InternalStuffBag[bag, i]], {i, n}];
InternalBagPart[bag, All]
],
CompilationTarget -> "C"
];

n = 10000000;
a = Reap[Do[If[EvenQ[i], Sow[i]], {i, n}]][[2, 1]]; // AbsoluteTiming // First
b = Rest[cf[n]]; // AbsoluteTiming // First
a == b


5.39257

0.214701

True

• I wonder, is there a specific advantage of using these undocumented "bags" instead of normal lists and AppendTo? Is there a difference in the grwoth behavior of lists and bags? Does Reap and Sow use bags internally? Sep 7, 2018 at 11:54
• @M.Winter, AppendTo will lead to quadratic complexity instead of linear, I would not recommend using AppendTo to build lists element-by-element. Sep 7, 2018 at 12:01
• @HenrikSchumacher cheater :) definitely +1. Maybe it is worth including a link to a SE question where InternalBag is explained in some more details, since it is undocumented functionality? Like this one mathematica.stackexchange.com/q/845/59438 Sep 7, 2018 at 12:10
• @M.Winter, in general, the idea is very simple: AppendTo makes a completely new expression and copies all elements form the original expression plus the new element, while Sow just marks an expression to be collected (filling some stack, I suppose), which are collected by Reap only once, at the end. Regarding Bags, I myself have discovered them only recently, I would recommend searching SE. SE can be called "The Documentation Centre for undocumented functions" :) Sep 7, 2018 at 12:16
• @M.Winter The main advantage of Bag is that it is compilable. Repeatedly appending to a list has quadratic complexity, but there are easy ways around this, e.g. using a linked list (which I can show you in another answer if you request it). However, these solutions are not Compileable, while Bag is. Sep 7, 2018 at 12:22