MapList Function

Question

Mathematica has a number of functions that return not only the end result or a single match, but all results. Such functions are called *List . Application:

• Foldlist
• Nestlist
• Replacelist
• Composelist

What I am missing is the MapList function.

For example, I want:

 MapList[f, {1, 2, 3, 4}] 

  {{f [1], 2, 3, 4}, {1, f [2], 3, 4}, {1, 2, f [3], 4}, {1, 2, 3, f [4 ]}} 

I need a list item for each function application:

 MapList[ f, {h[1, 2], {4, Sin[x]}}, {2} ] // Column 

  {h [f [1], 2], {4, Sin [x]}}
 {h [1, f [2]], {4, Sin [x]}}
 {h [1, 2], {f [4], Sin [x]}}
 {h [1, 2], {4, f [Sin [x]]}} 

---

You can implement this as:

 MapList[f_, expr_, level_: 1] := MapAt[f, expr, #] & /@ Position[expr, _, level, Heads -> False] 

However, this is quite inefficient. Consider this simple case and compare these timings :

 a = Range@1000 ; #^2 & /@ a // timeAvg MapList[#^2 &, a] // timeAvg ConstantArray[#^2 & /@ a, 1000] // timeAvg 0.00005088 0.01436 0.0003744 

This illustrates that, on average, MapList about 38X slower than the aggregate collection of function mapping for each item in the list and creating the 1000x1000 array.

---

Therefore, how can MapList be implemented as efficiently as possible?

Answer 1

I suspect MapList approaching a performance limit for any transformation that performs structural modification. Existing targets are not truly fair comparisons. The Map example is a simple integer vector. Example ConstantArray creates a simple vector of shared links to the same list. MapList does not illustrate these examples well because it creates a vector in which each element represents a fresh, undivided data structure.

I added two more tests below. In both cases, each element of the result is a packed array. The Array case generates new elements by adding a Listable to a . The Module case generates new elements, replacing one value in copy a . These results are as follows:

 In[8]:= a = Range@1000 ; #^2 & /@ a // timeAvg MapList[#^2 &, a] // timeAvg ConstantArray[#^2 & /@ a, 1000] // timeAvg Array[a+# &, 1000] // timeAvg Module[{c}, Table[c = a; c[[i]] = c[[i]]^2; c, {i, 1000}]] // timeAvg Out[9]= 0.0005504 Out[10]= 0.0966 Out[11]= 0.003624 Out[12]= 0.0156 Out[13]= 0.02308 

Note how the new tests work much more than MapList and are less like Map or ConstantArray examples. This, apparently, shows that there are not many opportunities for drastically improving MapList performance without some core core magic. We can shave the time off a MapList , this way:

 MapListWR4[f_, expr_, level_: {1}] := Module[{positions, replacements} , positions = Position[expr, _, level, Heads -> False] ; replacements = # -> f[Extract[expr, #]] & /@ positions ; ReplacePart[expr, #] & /@ replacements ] 

What gives these timings:

 In[15]:= a = Range@1000 ; #^2 & /@ a // timeAvg MapListWR4[#^2 &, a] // timeAvg ConstantArray[#^2 & /@ a, 1000] // timeAvg Array[a+# &, 1000] // timeAvg Module[{c}, Table[c = a; c[[i]] = c[[i]]^2; c, {i, 1000}]] // timeAvg Out[16]= 0.0005488 Out[17]= 0.04056 Out[18]= 0.003 Out[19]= 0.015 Out[20]= 0.02372 

This is included in Factor 2 of the Module case, and I expect that further microoptimizations can further close the gap. But I look forward to joining you, awaiting an answer that shows another tenfold improvement.

Answer 2

(Updated my function)

I think I can offer another 2x boost over the WReach attempt.

 Remove[MapListTelefunken]; MapListTelefunken[f_, dims_] := With[{a = Range[dims], fun = f[[1]]}, With[{replace = ({#, #} -> fun) & /@ a}, ReplacePart[ConstantArray[a, {dims}], replace] ] ] 

Here are the timings on my machine (Sony Z laptop, i7, 8 GB, 256 SSD in raid 0):

 a = Range@1000 ; #^2 & /@ a; // timeAvg MapList[#^2 &, a]; // timeAvg MapListWR4[#^2 &, a]; // timeAvg MapListTelefunken[#^2 &, 1000]; // timeAvg 0.0000296 (* just Mapping the function over a Range[1000] for baseline *) 0.0297 (* the original MapList proposed by Mr.Wizard *) 0.00936 (* MapListWR4 from WReach *) 0.00468 (* my attempt *) 

Answer 3

I think you still need to create a 1000x1000 array, and I don't think there is a smarter way than a constant array. Moreover, your examples are better served with the following definition, although I admit that he lacks the subtlety of the levels.

 MapList[f_, list_] := (Table[MapAt[f, #, i], {i, Length@ #}] &)@list; 

In your own definition, the culprit is calling Position[] , which creates a complex supporting structure.

Provide a more complex use case that better covers your intentions.