I have two functions $f$ and $g$. Given some order parameter $n$, I want to created all nested applications of $f$ and $g$ and save them in a list. For example, for order 1 we will have {f(x),g(x)}. For order 2 we have {f(f((x)),f(g(x)),g(f(x)),g(g(x))} and so in. In general, for order $n$ the list should contain $2^n$ items.


2 Answers 2


Using Composition:


comps[flist_List, n_ /; n > 0] := Module[
  {t = Tuples[flist, n]},
  Fold[Composition, #]@x & /@ t


comps[{f, g}, 1]

{f[x], g[x]}

comps[{f, g}, 2]

{f[f[x]], f[g[x]], g[f[x]], g[g[x]]}

comps[{f, g}, 4]

{f[f[f[f[x]]]], f[f[f[g[x]]]], f[f[g[f[x]]]], f[f[g[g[x]]]],
f[g[f[f[x]]]], f[g[f[g[x]]]], f[g[g[f[x]]]], f[g[g[g[x]]]],
g[f[f[f[x]]]], g[f[f[g[x]]]], g[f[g[f[x]]]], g[f[g[g[x]]]],
g[g[f[f[x]]]], g[g[f[g[x]]]], g[g[g[f[x]]]], g[g[g[g[x]]]]}

Also explore RightComposition.

  • $\begingroup$ Thank you for the answer! I will wait a bit before deciding which answer to accept. Both seem to work fine... $\endgroup$
    – JohnnyB
    Commented Mar 26 at 2:07

First level

a = {f[x], g[x]};

Second level

b = Flatten @ Transpose @ Query[All, {f, g}] @ a

{f[f[x]], f[g[x]], g[f[x]], g[g[x]]}

Subsequent levels

nesting[x_, n_] := Nest[Flatten @* Query[All, {f, g}], x, n]

nesting[b, 1]

{f[f[f[x]]], g[f[f[x]]],
 f[f[g[x]]], g[f[g[x]]], 
 f[g[f[x]]], g[g[f[x]]], 
 f[g[g[x]]], g[g[g[x]]]}

list = nesting[b, 2]

{f[f[f[f[x]]]], g[f[f[f[x]]]], f[g[f[f[x]]]], g[g[f[f[x]]]], 
 f[f[f[g[x]]]], g[f[f[g[x]]]], f[g[f[g[x]]]], g[g[f[g[x]]]], 
 f[f[g[f[x]]]], g[f[g[f[x]]]], f[g[g[f[x]]]], g[g[g[f[x]]]], 
 f[f[g[g[x]]]], g[f[g[g[x]]]], f[g[g[g[x]]]], g[g[g[g[x]]]]}

Another ordering:

SubsetMap[ReverseSort, SubsetMap[Sort, list, 1 ;; 8], 9 ;; 16]

{f[f[f[f[x]]]], f[f[f[g[x]]]], f[g[f[f[x]]]], f[g[f[g[x]]]], 
 g[f[f[f[x]]]], g[f[f[g[x]]]], g[g[f[f[x]]]], g[g[f[g[x]]]], 
 g[g[g[g[x]]]], g[g[g[f[x]]]], g[f[g[g[x]]]], g[f[g[f[x]]]], 
 f[g[g[g[x]]]], f[g[g[f[x]]]], f[f[g[g[x]]]], f[f[g[f[x]]]]}
  • $\begingroup$ Thank you for the answer! I will wait a bit before deciding which answer to accept. $\endgroup$
    – JohnnyB
    Commented Mar 26 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.