8
$\begingroup$

This question already has an answer here:

Occasionally I run into a Pattern that looks like i:func[arg_]:=i= an expression using arg

I have two questions on this:

  1. Can someone explain what this Pattern does? I do not understand the purpose of (if that is what is happening!) the subsequent application of setting the Pattern i as the Function func which then "redefines" i via SetDelayed and then some memoization (?) seems to be applied to i via Set.
  2. How could I have found this out myself? I could not get a clear understanding from Trace or inspecting func//DownValues neither did I find it in the Pattern[] entry in the documentation or Pattern related tutorials.

An example is given in peg solitaire. The Pattern used is:

i:findMoves[tab_]:=i=Flatten[#, 1]&[findMovesZero[tab, #]&/@Position[tab, 0]]

Another - more compact - one in an answer on: Using Memoization with a Mutable Object.

t : treeInsert[tree_, elem_] /; ! FreeQ[tree, elem] := t = tree
$\endgroup$

marked as duplicate by Mr.Wizard Jul 19 '16 at 8:21

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ @Jack LaVigne , Yes, I understand how to use the help system and I know : represents a Pattern (I actually refer to it in my question). However this seems more complicated as here the pattern is the Function func which subsequently again "defines" i via SetDelayed and then some memoization is applied to it via Set. At least that's what I see, which I doubt I understand correctly. $\endgroup$ – Sander Jun 22 '16 at 3:08
  • 3
    $\begingroup$ name:function[arg_]:=name=(do something with arg) is the same effect as function[arg_]:=function[arg]=(do something with arg) - it accomplishes "memoization" by dynamically defining a pattern with the computed result. The effect is documented in the tutorial "functions that remember their results" (or something like that), I don't recall if they show/use the first form there. $\endgroup$ – ciao Jun 22 '16 at 4:17
  • 1
    $\begingroup$ @Mr.Wizard I personally do not mind as I understand it now. However, I was aware of the memoization construct you described in your referred post and yet needed ciao to help me recognise "my" construct is (indeed) equivalent. I cannot comment on the value (if any) it may bring to others being equally puzzled. $\endgroup$ – Sander Jul 19 '16 at 7:53
  • 1
    $\begingroup$ Okay. Had you read my A note regarding syntax section (with mem :) and it was still not clear? If so I should rewrite that section for improved clarity. $\endgroup$ – Mr.Wizard Jul 19 '16 at 7:59
  • 1
    $\begingroup$ @Mr.Wizard, I missed it! Okay to close this one as duplicate. Only thing I can suggest is that it is a bit at the end for what I think is a very valuable alternative. $\endgroup$ – Sander Jul 19 '16 at 8:10
5
$\begingroup$

This is a form of memoization by dynamically defining a Pattern with the results of the executed Expression as clarified by @ciao.

The standard form is documented in Functions that remember values they have found and looks like:

f[x_]:=f[x]=rhs

So as an example:

f[x_] := f[x] = f[x - 1] + f[x - 2]

behaves the same as

i:f[x_] := i =  f[x - 1] + f[x - 2]

To demonstrate, this example comes from the referred documentation:

Clear[f];
f[x_] := f[x] = f[x - 1] + f[x - 2]
?f

f[x_]:=f[x]=f[x-1]+f[x-2]

DownValues@f

{HoldPattern[f[x_]] :> (f[x] = f[x - 1] + f[x - 2])}

f[0] = f[1] = 1;
?f
DownValues@f

f[0]=1

f[1]=1

f[x_]:=f[x]=f[x-1]+f[x-2]

{HoldPattern[f[0]] :> 1, HoldPattern[f1] :> 1, HoldPattern[f[x_]] :> (f[x] = f[x - 1] + f[x - 2])}

f[5];
?f
DownValues@f

f[0]=1

f[1]=1

f[2]=2

f[3]=3

f[4]=5

f[5]=8

f[x_]:=f[x]=f[x-1]+f[x-2]

{HoldPattern[f[0]] :> 1, HoldPattern[f1] :> 1, HoldPattern[f[2]] :> 2, HoldPattern[f[3]] :> 3, HoldPattern[f[4]] :> 5, HoldPattern[f[5]] :> 8, HoldPattern[f[x_]] :> (f[x] = f[x - 1] + f[x - 2])}

The following is the equivalent in the alternative form:

Clear[f]
i : f[x_] := i = f[x - 1] + f[x - 2]
DownValues@f

{HoldPattern[i : f[x_]] :> (i = f[x - 1] + f[x - 2])}

f[0] = f[1] = 1;
f[5];
?f
DownValues@f

f[0]=1

f[1]=1

f[2]=2

f[3]=3

f[4]=5

f[5]=8

i:f[x_]:=i=f[x-1]+f[x-2]

{HoldPattern[f[0]] :> 1, HoldPattern[f1] :> 1, HoldPattern[f[2]] :> 2, HoldPattern[f[3]] :> 3, HoldPattern[f[4]] :> 5, HoldPattern[f[5]] :> 8, HoldPattern[i : f[x_]] :> (i = f[x - 1] + f[x - 2])}

$\endgroup$
  • $\begingroup$ Very nicely answered! +1 $\endgroup$ – ciao Jun 22 '16 at 6:04
  • $\begingroup$ @ciao Thanks, could not have done it without you :) $\endgroup$ – Sander Jun 22 '16 at 7:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.