# Selecting expressions from a sequence that are not subexpressions of earlier elements

I have a While loop that generates and prints an expression on each iteration (there can be thousands of iterations). UPDATE: Some expressions are generated in unevaluated form (e.g. 1 + 1) and printed in this form. This behavior should be kept in the modification explained below.

I want to modify it to print only new expressions — that do not appear as sub-expressions of any expression that has been generated at an earlier step. We assume that any expression is a sub-expression of itself, so no expression should be printed twice. Generated expressions may contain patterns, and they should be handled verbatim (each symbol represents only itself). For example:

(* Iteration 1 *)
f[_] (* PRINTED *)

(* Iteration 2 *)
f (* Skipped *)

(* Iteration 3 *)
_ (* Skipped *)

(* Iteration 4 *)
Blank (* Skipped *)

(* Iteration 5 *)
f[0] (* PRINTED *)

(* Iteration 6 *)
f[_] (* Skipped *)

(* Iteration 7 *)
g[f[0]] (* PRINTED *)


What is the most efficient way to maintain a set of expressions that have been already printed and validate newly generated expressions against this set?

-
By unevaluated form you mean Unevaluated? Because part "(e.g 1+1)" suggest it is rather Defer. – Kuba Dec 9 '13 at 8:58
Print[Unevaluated[1+1]] prints 1+1 but if we do for example expr={Unevaluated[1+1]}, Print[First@expr] prints as Unevaluated[1+1]. I think this is the problem, but I haven't got a solution. – C. E. Dec 9 '13 at 13:08
All generated expressions are wrapped in HoldForm. – Laila Podlesny Dec 9 '13 at 20:18

Try this and let me know if there are cases it misses:

exprs = {f[_], f, _, Blank, f[0], f[_], g[f[0]]};
taken = {};
Do[
If[! MemberQ[taken, Verbatim[i]], Print[i]];
taken = Union[{Head[i]}, Level[i, {0, Infinity}], taken];
, {i, exprs}]

(* Out:
f[_]
f[0]
g[f[0]] *)

-
Sorry, I forgot to mention that some expressions are in unevaluated form. I updated my question. – Laila Podlesny Dec 9 '13 at 0:33