3
$\begingroup$

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}*), ...}
$\endgroup$
4
$\begingroup$
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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – KHAAAAAAAAN May 14 at 18:11
  • $\begingroup$ 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. $\endgroup$ – Roman May 14 at 18:24
  • $\begingroup$ 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]}. $\endgroup$ – KHAAAAAAAAN May 14 at 18:43
  • $\begingroup$ 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. $\endgroup$ – KHAAAAAAAAN May 14 at 18:45
  • $\begingroup$ 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}*), ...} $\endgroup$ – KHAAAAAAAAN May 14 at 18:49
1
$\begingroup$

"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]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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