# Passing large list by reference

I have the following problem: I would like to control evaluation of a variable that points to a list. For example, frequently in the code I have functions of the form that are supposed to work on large lists (modifying them frequently):

updateList[list_, newvalue_, index_]:= (list[[index]] = newvalue)


to be used (many times) as

list = {1, 2, 3};
While[...
updateList[list, -2, 2];
]


and I should get immediately

list = {1, -2, 3}


The problem is that the list gets evaluated immediately if one is not careful and the assignment statement fails. I have tried to solve this by defining

Attributes[updateList] = {HoldAll}


It works, but I realized that this can get very complicated since I am passing the list quite a bit around in a rather big package. Some function have Hold, some not, on some I would actually like to have the second and the third argument Holding while others not... To tell you the truth, I do not feel I have the control of this behavior; sometimes it evaluates and sometimes it does not, and it is driving me crazy.

The reason why I am doing this is to save memory. One could, of course, use the following definition

updateList[list_, newValue_, index_] := (newList = list; newList[[index]] = newvalue)


and use it like

list = updateList[list, -2, 2]


to the same effect, but this will consume quite a bit of memory (my list are huge). So I am trying to control memory usage by updating storage. I guess I am trying to use them as pointers.

A more serious example would be

updateList[list_, args__] :=
Block[{indicies, newvalues},
indicies = figureOutIndiciesToChange[args];
newvalues = figureOutValuesToChange[args];
list[[indicies]] = newvalues
];


or even a more nasty example (actually happens):

updateList[list_, args__] :=
Block[{indicies, newvalues},
indicies = figureOutIndiciesToChange[args];
nestedCallToUpdateTheList[...., list, ...];
newvalues = figureOutValuesToChange[args];
list[[indicies]] = newvalues
];


where

(* here list can be third argument, or even last *)
nestedCallToUpdateTheList[...., list_, ...] :=
While[a big loop,
list[[dynamicIndicies] = dynamicValues]];
]


So I have a principle (open) question: how to update long lists (parts of it) in the most efficient way if such lists are passed through several layers of functional calls? Is there a way to achieve this without using HoldAll? Perhaps using more direct Hold functionality? Anyway, I would like to learn how to be in control...

EDIT1: Based on the comments below, I would like to add another requirement; Assume that all this has to be done within the function. Is this possible at all? A bullet-proof way would be

updateLilst[___] := fail["please used Hold on the list argument"];
updateList[...,list_Hold,...] := do the work on the list;


Or...?

EDIT2: By the way, how to test whether an argument is evaluated in the function?

p.s. I tried with Hold, but it is tricky since it is not make the assignment with a Held variable...

-
What's the reason for using a function in the first place instead of running list[[2]]=-2 directly to modify the list? tutorial/AddingRemovingAndModifyingListElements –  ssch Feb 11 '13 at 19:30
it has to be done programatically due to the nature of the problem. I am solving numerically equations of motion for a dynamical system. at every time step these lists have to get incrementally updated. there is no problem when one clones the list while updating it. the key issue is how to do it without cloning the list. –  zorank Feb 11 '13 at 19:32
The FullForm of the previous is: Set[Part[list, 2], -2] if you prefer that notation. And neither clones the list, after: list = {1, 2, 3, 4, 5}; list[[2 ;; 3]] = -1; list will be modified so list=={1,-1,-1,4,5} –  ssch Feb 11 '13 at 19:33
I know. The problem is that when you start passing it around in many funcitons it can get tricky. For example, updateList function will break down if its attributes are not defined to HoldAll on the list. –  zorank Feb 11 '13 at 19:39
You may find this paper by Robby Villegas and interesting read. –  Szabolcs Feb 11 '13 at 22:01

Would this work for you?

makeList[symb_, l_] := Module[{x},
symb /: list[symb] := x;
symb /: updateList[symb, spec_, val_] := (x[[spec]] = val);
symb /: listParts[symb, spec_] := (x[[spec]])
x = l;
symb
]


After doing

makeList[foo,{1,2,3}]


the list is stored in a "local" variable x$42 (the specific number is chosen by mathematica). You can pass around the symbol foo without having to worry about x$42 being accidentally evaluated. You can access and update the list via list, updateList and listParts.

Along those lines, you could also do the following (disclaimer: redefining Set and Part is probably a bad idea):

caveatEmptor[symb_] := Module[{x},
Unprotect[Set];
Unprotect[Part];
Set[symb, val_] := Set[x, val];
Set[Part[symb, spec__], val_] := Set[Part[x, spec], val];
Part /: Part[symb, spec__] := Part[x, spec];
show[symb] := x;
Protect[Set];
Protect[Part];
]


After running

caveatEmptor[foo]


the following appear to behave as normal:

foo={1,2,3}
foo[[2]]=4
foo[[2;;3]]


but foo is still an undefined symbol so you can pass it without worry of evaluation. You have to do

show[foo]


to see the value you set.

-
I put in the TagSetDelayed (/:) so that you could get rid of the definitions by doing Remove[foo]. I'm not sure how this will affect performance. –  Tobias Hagge Feb 12 '13 at 6:37
This is indeed very close what I would like to achieve. In principle, if I understand correctly, you have defined an object called list. Smart! I wish it was my idea... Have to think though how would it apply to my problem, but looks very, very close. Many thanks! –  zorank Feb 12 '13 at 10:55
I agree that modifying Set/Part is not such a good idea. Though one might try to create own versions of these commands. This would make the code much more readable actually. Thanks! –  zorank Feb 12 '13 at 11:01
Could you not set UpValues to Set and Part instead of Unprotect then? +1 –  Murta Feb 15 '13 at 10:12
@Murta: If I use TagSetDelayed on the fifth line, symb appears too deep for an assigned rule to be found. The upvalue in the sixth line is needed; mathematica does not like to do x[[3]]:=y[[3]]. –  Tobias Hagge Feb 15 '13 at 16:24

Only to answer a specific point, because it is too large to fit in the comments.

You say

on some I would actually like to have the second and the third argument Holding while others not

You can pass specific arguments by what is called "by reference" in other languages, while passing the others by value. So you do not have to make the whole function HoldAll. This is done by requiring the caller to wrap the argument itself with Unevaluated. This makes the wrapped argument pass by reference while others pass by value (the default).

foo[a_, b_, c_] := Module[{tmpA = a, tmpC = c},
tmpA[[2]] = 5;
b[[2]] = 5;
tmpC[[2]] = 5;
{tmpA, b, tmpC}
]
a = Table[1, {10}]; b = a; c = a;
{a, b, c} = foo[a, Unevaluated[b], c]


Btw, This is actually not a good way to do things, and I do not use this method any more, but did use once or twice before.

This can make things confusing when looking at the function itself, as there is no indication inside the function that some input(s) should be passed by reference and some by value. It also can have some other bad side-effects and might not be too robust for all uses. So I am not suggesting this method, just saying it is there to look at.

-
this was very good idea. perhaps one could try to define foo[a_, b_Unevaluated, c_] := ... with foo[___] := fail to ensure that the caller is doing its part of the bargin? –  zorank Feb 12 '13 at 11:04
@zorank The Unevaluated wrapper will be eated on evaluation of the enclosing function. But you can check that the symbol is unevaluated by foo[a_, b_Symbol, c_]. –  Alexey Popkov Feb 12 '13 at 17:49

You can set the attribute HoldFirst to only hold the first argument. And define the function such that it only accepts a symbol since you can't do things like:

{1,2,3}[[1]]=9


The code:

Clear[updateList];
Attributes[updateList] = {HoldFirst};
updateList[list_Symbol, value_, index_] := (list[[index]] = value;)

i = 1; val = 2;
list = {0, 0, 0};
updateList[list, val, i]
list
(* {2,0,0} *)


If you try to supply a list directly:

updateList[{1, 2, 3}, 2, 1]


It will remain unevaluated as updateList[{1, 2, 3}, 2, 1], but imo it'd be better to throw an error.

In the end you are left with something that's just a limited version of list[[i]]=val

-
Thank you for trying to help me out. Indeed, I am aware of the HoldFirst command. The problem is that it gets very tricky when there are many nested functinal calls and the list variable ends up being third or fourth argument way down... Also, there might be optional arguments etc. I would just like to learn how to exercise a firm controll of the beast :) Thanks for trying! –  zorank Feb 11 '13 at 20:12

A solution a la Tobias Hagge:

makeList[___] := invalidInvocation;
makeList[symb_Symbol,list_]:=
Block[{pointer, initialized, spec, val, temp},
initialized = listInitialized[symb]===True;
If[initialized,
Print["removeList before re-initializing it"];
Abort[]
];
pointer=Unique["listStorage$"]; temp = { Hold[pointer=Evaluate@list], Hold[symb/:listExtractElements[symb]:=pointer], Hold[symb/:listUpdateElements[symb,spec_,val_]:=(pointer[[spec]]=val)], Hold[symb/:listExtractParts[symb,spec_]:=(pointer[[spec]])], Hold[symb /:removeList[symb] := (Remove[pointer]; Unprotect[symb];Remove[symb])] }; Map[ReleaseHold[# /. OwnValues[pointer]]&, temp]; symb/:listInitialized[symb]:=True; Protect[symb]; Null ];  Note: I use Block since the function will be called many times. We create a list In[3]:= makeList[list, {1,2,3}] In[4]:= Definition[list] Out[4]= Attributes[list]={Protected} listExtractElements[list]^:=listStorage$3
listInitialized[list]^:=True
removeList[list]^:=(Remove[listStorage$3];Unprotect[list];Remove[list]) listUpdateElements[list,spec_,val_]^:=listStorage$3[[spec]]=val
listExtractParts[list,spec_]^:=listStorage$3[[spec]]  If we try to make it again it will complain. In[5]:= makeList[list, {1,2,3}] ...removeList before re-initializing it Out[5]=$Aborted


If we try to assign a value to it it will complain

In[6]:= list = 1
During evaluation of In[6]:= Set::wrsym: Symbol list is Protected. >>
Out[6]= 1


we can only operate on it by the methods we have defined

In[7]:= listUpdateElements[list, 2, newElement]
Out[7]= newElement
In[8]:= listExtractElements[list]
Out[8]= {1,newElement,3}


Only if we remove it explicitly

In[9]:= removeList[list]


we can assign values to it

In[10]:= list = 1
Out[10]= 1


If we try to make a list on already assigned symbol it will complain

In[11]:= makeList[list, {2, 3, 5}]
Out[11]= invalidInvocation


The symbol has to be clean, then assignemnt can be done

In[12]:= Clear[list]
In[13]:= makeList[list, {2, 3, 5}]
In[14]:= listExtractElements[list]
Out[14]= {2,3,5}


Many thanks Tobias! This was a brilliant suggestion. A foolproof concept with absolute controll of what is going on.

Zoran

-