Applying a function with the HoldAll attribute inside NestList

Question

I'm trying to write an update function, which can be applied to a list and then to NestList it.

As the function has to manipulate the given variable I figured I need HoldAll or HoldFirst, so the variable is passed by reference.

update[x_] := (x[[1]] = x[[1]]*2; x)
Attributes[update] = HoldAll;

This works:

mylist = Table[3, {i, 1, 3}]; update[mylist]

It gives:

{6,3,3}

But now I want it to be nested in a list. The code

NestList[update, mylist, 3]

should give

{{6,3,3},{12,3,3},{24,3,3},{48,3,3}}

but it gives

Set::setraw: Cannot assign to raw object 12. 
Set::setraw: Cannot assign to raw object 12. 
Set::setraw: Cannot assign to raw object 12. 
General::stop: Further output of Set::setraw will be suppressed during this calculation.

{{12,3,3}, {12,3,3}, {12,3,3}, {12,3,3}}

Am I right that this is happening because NestList evaluates mylist before applying update? If so, how can I stop this? I can't set Attributes[NestList] = HoldAll; , right?

Any help is appreciated :)

Cheers :D

Answer 1

Indeed, Nest and NestList do not support functions with Hold attributes (as well as Fold and FoldList, etc). There were discussions of this in the past. I was able to find one such.

As far as I can tell, this is by design. What happens is that NestList (for example) maintains an internal list of intermediate results, the last of which is used in the next iteration. This list is not exposed to the user in any case, so there is no way that the user can mutate it. For the same reason setting NestList as HoldAll won't help (except may be the very first iteration).

Besides, one can argue that allowing for mutable state for operations like Nest would make them less pure. And you can in any case introduce such state by re-defining your update function as a closure, with the mutable state (your variable) embedded into it (although in the present context it won't make much sense):

updateMyList[] := (myList[[1]] = myList[[1]]*2; myList)

or you can generate this as a pure function:

NestList[Function[(myList[[1]] = myList[[1]]*2; myList)], myList,3]

where in both cases the actual value fed to the function is simply ignored.

That said, you can easily implement your own versions of these functions which would have different semantics regarding Hold* functions. Here is an example:

ClearAll[nestlist];
nestlist[f_, start_, n_] :=
  Module[{current = start, tag},
    Prepend[
     If[# === {}, {}, First@#] &@
        Reap[Do[Sow[current = f[current], tag], {n}], tag, #2 &][[2]],
     start]];

and you can create similar implementations for other functions.

However, as I said, to me this problem indicates rather that you have to reconsider your design and perhaps use iterative constructs such as loops explicitly, since the essence of your desired operation has more of a procedural flavor (mutable state is essential) than functional one.

Answer 2

update[x_] := (x[[1]] = x[[1]]*2; x)
Attributes[update] = HoldAll;

list = Range[3];

That first evaluation of list in Nest[update, list, 5] is an issue but it's not the main issue. If that was the issue it could be solved with Nest[update, Unevaluated@list,5]. However, this would only work in the first iteration.

Nest applies the function to the result of the previous one. The result of update[list] is the list itself, not the variable. How could otherwise Mathematica know that you don't want update[(list[[1]]=list[[1]]*2;list)] which would be a mess? You should take care to return something inert

newUpdate[Hold[x_]] := (x[[1]] = x[[1]]*2; Hold[x])

list = Range@4;
Nest[newUpdate, Hold@list, 4];
list

(* {16, 2, 3, 4} *)

Answer 3

Continuing the theme that Rojo started, the main problem as I see it is that you are confounding the input to your function, the symbol name mylist, with the output of your function, a list of numbers. Since the symbol name does not change there is no reason for nesting, and you want simple iteration performed by Table:

ClearAll[update, mylist]

update[x_] := (x[[1]] = x[[1]]*2; x)
Attributes[update] = HoldAll;

mylist = {3, 3, 3};

Table[update[mylist], {4}]

{{6, 3, 3}, {12, 3, 3}, {24, 3, 3}, {48, 3, 3}}

Since you are generating a list of results there is little point to in-place modification as seen in your original update function, and a natural use of NestList would be something like:

f[x_] := MapAt[2 # &, x, 1]

NestList[f, {3, 3, 3}, 4]

{{3, 3, 3}, {6, 3, 3}, {12, 3, 3}, {24, 3, 3}, {48, 3, 3}}