# Transform a list of functions to a composition

How do I apply a list of functions in a nested way?

Example:

functionList = {f1,f2,f3}

RequiredCommand[functionList,Pi]


such that the required command returns

f3[f2[f1[Pi]]]


or f1[f2[f3[Pi]]] (reversing the order is easy)

I'm searching for an efficient way.

-

You'll want Composition[] or ComposeList[] for the purpose:

ComposeList[{f1, f2, f3}, x]
{x, f1[x], f2[f1[x]], f3[f2[f1[x]]]}

Composition[f3, f2, f1][x]
f3[f2[f1[x]]]


Since OP wants to be able to feed a list:

(Composition @@ {f3, f2, f1})[x]
f3[f2[f1[x]]]

-
ComposeList computes more than I need. Composition does not accept a list as argument, only a sequence. Consequently, I suggest using Composition[Sequence @@ #][x] &[functionList]. Please confirm that this completes your answer. – J. C. Leitão Apr 12 '13 at 12:04
@J.C.Leitão a cleaner way to do what you suggest is Composition[##][x] & @@ functionList, or rather (Composition[##] & @@ functionList)[x] – Jacob Akkerboom Apr 12 '13 at 12:06
@JacobAkkerboom aha, I didn't knew that. Thanks! – J. C. Leitão Apr 12 '13 at 12:07
@Jacob, (Composition @@ {f3, f2, f1})[x] is much cleaner, I'd think... – J. M. Apr 12 '13 at 12:13
Woops, ok that was silly, I blame the x "in between" ;). @J.C.Leitão see the solution above by J.M. ! – Jacob Akkerboom Apr 12 '13 at 12:25

You can use also Fold or FoldList, e.g.

Fold[ #2[#1] &, Pi, functionList]

f3[f2[f1[Pi]]]

FoldList[ #2[#1] &, Pi, functionList]

 {Pi, f1[Pi], f2[f1[Pi]], f3[f2[f1[Pi]]]}

-
Haha, or Through[FoldList[Composition, Identity, {f1, f2, f3}][Pi]] – Jacob Akkerboom Apr 12 '13 at 11:41
Your solution isn't simpler so I can't say haha. – Artes Apr 12 '13 at 13:27
I was merely trying to point out how similar your answer becomes to the above when you put in Composition. My piece of code makes a list of functions intermediately which none of the answers does... but its silly, hence the haha.. – Jacob Akkerboom Apr 12 '13 at 14:01
Ah, now I see the real added value of your answer, I thought Composition would behave similarly to Fold, but in fact it "calls" all its functions on its argument right away. So your solution manages the stack in a nicer way. But again I wasn't trying to discredit you, though maybe writing #2[#1] as Composition seemed a bit ironic. – Jacob Akkerboom Apr 12 '13 at 14:25
#2@#1& should also work. – J. M. Apr 12 '13 at 15:44

Since you said reverse-order input is OK, we can do this:

Compose[##, Pi] & @@ {f3, f2, f1}

f3[f2[f1[Pi]]]


Compose is deprecated but I still use it, and sometimes it performs better than alternatives.

-
I still wish they'd just rename Composition[] to Compose[]... – J. M. Apr 12 '13 at 17:47
@J.M. I can't say I agree, unless you support a rewrite of many other function names in a non-backward-compatible way; a language v2.0 of sorts. – Mr.Wizard Apr 12 '13 at 17:48
Hm... Compose "calls all its functions" in one swoop on the last argument, like "a Composition" does (on its one arguments). I would be interested in an example where it is really faster. See my answer here (below) – Jacob Akkerboom Apr 12 '13 at 23:18
@Jacob I was thinking of this. I also like terse coding as I'm sure you've observed. – Mr.Wizard Apr 12 '13 at 23:29
@Mr.Wizard Haha you won me over with your terse coding a long time ago :). Wow amazing Q&A, I'll look into it further later! – Jacob Akkerboom Apr 12 '13 at 23:46

As described in the other answers, Composition or Compose is what you need. Since you also wanted them to be applied in reverse order, the new RightComposition that is in the Wolfram Language is the appropriate function (of course, you can always Reverse the list before feeding to Composition).

functionList = {f1, f2, f3};
(RightComposition @@ functionList)[x]
(* f3[f2[f1[x]]] *)


Or using the infix notation:

f1 /* f2 /* f3 @ x

-

Consider the following timings

identitiesImplicit = ConstantArray[# &, 10000];
First /@
{
Timing[Compose[##, Pi] & @@ identitiesImplicit],
Timing[(Composition @@ identitiesImplicit)[Pi]],
Timing[Fold[#2[#1] &, Pi, identitiesImplicit]],
Timing[Last[ComposeList[identitiesImplicit, Pi]]]
}


-> {0.014458, 0.012889, 0.008957, 0.004041}

My explanations: Fold and ComposeList prevent copying of the data. ComposeList and Fold handle the stack nicely, whereas Compose and Composition do not. The fact that ComposeList stores values intermediately takes hardly any time at all (compare CompoundExpression with Last[List[##]]& for large sets of instructions). As ComposeList is an internal function that does exactly what it should except only for intermediate storing that takes little time, it performs best.

Copying the data does take a little time, as well as precious memory of course, as can be observed by comparing the results of the code below by that above. It is not very noticable, but this is not the most extreme example. In what is below, no coping of the long list of functions occurs.

iIS = Sequence @@ identitiesImplicit;
First /@
{
Timing[Compose[iIS, Pi]],
Timing[Composition[iIS][Pi]],
Timing[Fold[#2[#1] &, Pi, {iIS}]],
Timing[Last[ComposeList[{iIS}, Pi]]]
}


-> {0.011800, 0.011225, 0.008991, 0.004181}

Of course, it is not very feasible to pass around Sequences just to avoid this kind of copying of data, so Fold and Composition have an advantage here.

To see what I mean by "does not copy the data", consider the following

{
Clear[identitiesImplicit, iIS];
MemoryInUse[],
identitiesImplicit = ConstantArray[# &, 100000];
MemoryInUse[],
iIS = Sequence @@ identitiesImplicit;
MemoryInUse[],
aaa = {iIS};
"no memory increase",
MemoryInUse[]
}


-> {44769848, 45570024, 46370120, "no memory increase", 46370024}

-
I don't know if I understand the points you are making. (You keep editing the post for one thing.) Surely methods that apply functions one at a time such as Fold and ComposeList cannot be considered equivalent to methods that apply the functions all at once such as Compose and Composition. Perhaps that is part of what you are communicating? – Mr.Wizard Apr 12 '13 at 23:45
@Mr.Wizard ah.. yes indeed. That was the main point. I guess I put too much emphasis on this copying of the data thing. That is also harder to explain. It is something I found out about recently. I wanted to write something about it, but I got downvoted pretty soon as it resulted in a chaotic answer. If this does not look familiar to you maybe it deserves a self answered question. But note that it is very late where I am :). – Jacob Akkerboom Apr 12 '13 at 23:50
@Mr.Wizard it is similar to how linkedlists work. You can take part of them without copying that part in the memory. As a Sequence is a headless expression, you can put a list around a sequence and store that in a variable, without increasing how much memory you are using. A reference is being made to the Sequence. Goodnight! :) – Jacob Akkerboom Apr 12 '13 at 23:53
Why not (Composition @@ identitiesImplicit)[Pi]? – J. M. Apr 13 '13 at 0:16
Interesting observations, but your method of measurement renders the conclusions not entirely solid. Timings should be taken for repeated invocations taking at least a second and memory usage should be measured using MaxMemoryUsed[code]. With this approach Fold is clearly slowest and aaa = {iIS} is seen to involve a (temporary) copy. Still, the main conclusion as I see it (i.e. Composition[Last, ComposeList] is actually faster than Composition) is certainly interesting, so +1. :) – Oleksandr R. Apr 22 '13 at 5:00