Applying FoldList to its own output

I'm trying to figure out a functional way to essentially apply FoldList (or some related function such as Nest or ListCorrelate) to its own output. By this, I mean given some initial a and some total length, I want to generate the following list

{a, f[a], f[a,f[a]], f[a,f[a],f[a,f[a]]], ...}


However, there is an additional complexity that as the function f will ultimately have some randomness involved, I don't want each new call to f[a] to be a new execution of the function f, but rather to simply call the values which have already been calculated in previous indices. In other words, I am looking for a functional way to apply the function f to all elements left of the current element being calculated, with scalability to large list lengths in mind.

I've managed to implement this via recursion relations, but its a bit cumbersome and can get slow for large lengths. Any help would be greatly appreciated.

Edit Roman had an excellent answer below, but I'm now looking to try and implement a more complex version of this code. I'll add a bit of a clarification of the form of f to hopefully make my goal clearer - this is copied from a comment below:

The function f takes two inputs, a single value f0, and a list L. It then does a slightly random calculation which relies on both f0 and all values in L, and then generates a new value f1 and a new value, e. The output of f is then the list {f1,Append[L,e]}.

A sample output of what I'm looking for, with inputs a1 and {e1}:

{{a1, {e1}}, f[a1, {e1}] (*={a2,{e1,e2}}*), f[a2, {e1, e2}](*={a3,
{e1,e2,e3}*), f[a3, {e1, e2, e3}](*={a4,{e1,e2,e3,e4}*), ...}


Nest[Append[#, f @@ #] &, {a}, 3]


{a, f[a], f[a, f[a]], f[a, f[a], f[a, f[a]]]}

For the second part of your question I think it would be easier to define your function f such that the list appending is performed inside f: for example, a function that from a number a and a list of $$e$$-values elist calculates new numbers anew and enew (here symbolized by RandomReal[] but should really do your calculation):

f[a_, elist_] := Module[{anew, enew},
anew = RandomReal[];
enew = RandomReal[];
{anew, Append[elist, enew]}]

NestList[Apply[f], {a0, {e0}}, 3]


{{a0, {e0}}, {0.425748, {e0, 0.268434}}, {0.248881, {e0, 0.268434, 0.983386}}, {0.945438, {e0, 0.268434, 0.983386, 0.546319}}}

If you're only interested in the last member of this output, replace NestList with Nest.

• This is an excellent answer - and just what I needed. I'm now trying to implement a more generalized version which can deal with two inputs, and for f having two outputs. I've edited my question above - any ideas on how to implement this in a similar way to your above answer? – KHAAAAAAAAN May 14 '19 at 18:11
• For the second part of your question, I'm a bit confused as to what exactly you want. Could it be that the same solution works but replacing a with a list of two elements {a,b}? Something like Nest[Append[#, f @@ #] &, {{a, b}}, 3] generating {{a, b}, f[{a, b}], f[{a, b}, f[{a, b}]], f[{a, b}, f[{a, b}], f[{a, b}, f[{a, b}]]]}. You'll have to define the function f correspondingly, to accept a sequence of number pairs instead of a pair of number lists. Let me know if this is the right direction. – Roman May 14 '19 at 18:24
• Not quite - in concrete terms, the function f takes two inputs, a single value f0, and a list L. It then does a slightly random calculation which relies on both f0 and all values in L, and then generates a new value f1 and a new value, e. The output of f is then the list {f1,Append[L,e]}. – KHAAAAAAAAN May 14 '19 at 18:43
• Like I said, I have this implemented via memoization/recursion, and can think of pretty straightforward ways to do it via loops, but as the number of calculations will need to be in the tens of thousands, I think both loops/recursion are not quite efficient enough. – KHAAAAAAAAN May 14 '19 at 18:45
• Maybe this sample output will make it clear what I'm looking for, with inputs a1 and {e1}: {{a1, {e1}}, f[a1, {e1}] (*={a2,{e1,e2}}*), f[a2, {e1, e2}](*={a3,{e1,e2,e3}*), f[a3, {e1, e2, e3}](*={a4,{e1,e2,e3,e4}*), ...} – KHAAAAAAAAN May 14 '19 at 18:49

"I don't want each new call to f[a] to be a new execution of the function f, but rather to simply call the values which have already been calculated in previous indices"

It looks like memoisation will accomplish this, e.g.

f[x_] := f[x] = x + y
y = 0.1;
NestList[f, a, 4]


{a, 0.1 + a, 0.2 + a, 0.3 + a, 0.4 + a}

Clear[y]
NestList[f, a, 4]


{a, 0.1 + a, 0.2 + a, 0.3 + a, 0.4 + a}

Without any value for y, f has called the previously calculated values.

f[a + 0.3]


0.4 + a

Also see DownValues[f]