# 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. Commented Apr 12, 2013 at 12:04
• @J.C.Leitão a cleaner way to do what you suggest is Composition[##][x] & @@ functionList, or rather (Composition[##] & @@ functionList)[x] Commented Apr 12, 2013 at 12:06
• @JacobAkkerboom aha, I didn't knew that. Thanks! Commented Apr 12, 2013 at 12:07
• @Jacob, (Composition @@ {f3, f2, f1})[x] is much cleaner, I'd think... Commented Apr 12, 2013 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. ! Commented Apr 12, 2013 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]] Commented Apr 12, 2013 at 11:41
• Your solution isn't simpler so I can't say haha. Commented Apr 12, 2013 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.. Commented Apr 12, 2013 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. Commented Apr 12, 2013 at 14:25
• #2@#1& should also work. Commented Apr 12, 2013 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[]... Commented Apr 12, 2013 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. Commented Apr 12, 2013 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) Commented Apr 12, 2013 at 23:18
• @Jacob I was thinking of this. I also like terse coding as I'm sure you've observed. Commented Apr 12, 2013 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! Commented Apr 12, 2013 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? Commented Apr 12, 2013 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 :). Commented Apr 12, 2013 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! :) Commented Apr 12, 2013 at 23:53
• Why not (Composition @@ identitiesImplicit)[Pi]? Commented Apr 13, 2013 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. :) Commented Apr 22, 2013 at 5:00