# About minimizing calculations when using ComposeList

I have a lot of functions to use in a iterative way, and I need some of the calculation results. For example:

 func = Function[{s}, s Sin[#] &] /@ Range[100];
ComposeList[func, x][[1 ;; ;; 10]]


Apparently, this code calculates much more than necessary. Especially, a lot of time is needed for the calculation when the length of func list is very long and when the Function is very complicated (e.g. Length@func = 1024 and the function is Fourier);

Is there any elegant way to reduce the calculation?

Edit

Perhaps I should say more about the fact that this code calculates than necessary.

For example,

  func = Function[{s}, s Sin[#] &] /@ Range[10];
result=ComposeList[func, x][[1 ;; ;; 5]]


(*

{x, 5 Sin[4 Sin[3 Sin[2 Sin[Sin[x]]]]], 10 Sin[9 Sin[ 8 Sin[7 Sin[6 Sin[5 Sin[4 Sin[3 Sin[2 Sin[Sin[x]]]]]]]]]]}

*)

Now we can see that result[[2]] (i.e., 5Sin[4 Sin[3 Sin[2 Sin[Sin[x]]]]]) is also appeared inside result[[3]] (i.e., 10Sin[...5Sin[4 Sin[3 Sin[2 Sin[Sin[x]]]]]], so the evaluation for 5Sin[4 Sin[3 Sin[2 Sin[Sin[x]]]]] is repeated twice here.

The repetition will be very large with an increase of Length[func], which will be much more time-consuming than it is required. This is my point here (Up to now, Rojo has gotten the point and solved it ).

-
Doesn't Table[(Composition @@ Reverse[Take[func, k]])[x], {k, 0, 100, 10}] do what you want? –  Ｊ. Ｍ. Jul 7 '12 at 6:49
"Apparently, this code calculates much more than necessary." -- what leads you to believe that? ComposeList is normally quite efficient. Is there some symbolic pre-simplification that you what to leverage in your application? –  Mr.Wizard Jul 7 '12 at 10:10
@J.M && Mr.Wizard, the code proposed by J.M works well, but with the same problem as mine. (i.e., 10 Sin[9 Sin[8 Sin[7 Sin[6 Sin[5 Sin[4 Sin[3 Sin[2 Sin[Sin[x]]]]]]]]]] will be caculated many times if Length@@func is very large, that is the problem I want to get rid of.) –  yulinlinyu Jul 7 '12 at 12:24
What is your evidence that it is calculated many times? Each function is only applied once, to the result of the previous function application. –  Mr.Wizard Jul 7 '12 at 14:11
@Mr.Wizard, See my edit. –  yulinlinyu Jul 7 '12 at 14:36
show 1 more comment

I am not sure I understood the problem but I have the hunch that the best answer is: no it won't calculate that many times. If the source of inefficiency you see is the fact of getting 9 out of 10 intermediate results are being dropped in the end, I see the point.

If this is the point, then you could do

ComposeList[
Composition @@@ Reverse /@ Partition[func, 10, 10, 1, {}], x]


Otherwise, you're mistaken... Try, for example,

func = Function[{s}, s (Print[#]; Sin[#]) &] /@ Range[10];
ComposeList[func, x]


and see how you get each function evaluated only once, and you don't get the innermost Sin evaluated 10 times (if that was the case, the Print would be evaluated with it since both are part of the same function)

-
,thank you very much, the code ComposeList[ Composition @@@ Reverse /@ Partition[func, 10, 10, 1, {}], x] is just what I want. I'm sorry for the words limits in the comment. See more explanations in the next comment. –  yulinlinyu Jul 7 '12 at 14:02
(Continued)I have use NestList[Nest[f, #, k] &, start, n] proposed by J.M. (seen here link) when the iterative function is the same (it is Sin in my example in NestList[Nest[f, #, k] &). Now here the function is not the same (it is Function[{s}, s Sin[Sow[#]] &]). Your solution in this post resembles very much with NestList[Nest[f, #, k] & proposed by J.M., and I think it is very interesting. –  yulinlinyu Jul 7 '12 at 14:02

Maybe Reap and Sow could be used here:

func = Function[{s}, s Sin[Sow[#]] &] /@ Reverse@Range[100];

lst = Reap[(Composition @@ func)[x]];

lst[[2, 1]][[1 ;; ;; 10]]


The Composition is walked through only once, and we collect the intermediate results in passing. Not sure if this more elegant - with the example you give, the result in Reap looks the same as what your ComposeList` would have produced.

-