6
$\begingroup$

I found myself writing memoizing code like this:

p[k1_] := p[k1] = b^0 a[k1];
p[k1_, k2_] := p[k1, k2] = p[k1] + b^1 a[k1 + k2];
p[k1_, k2_, k3_] := p[k1, k2, k3] = p[k1, k2] + b^2 a[k2 + k3];
p[k1_, k2_, k3_, k4_] := 
  p[k1, k2, k3, k4] = p[k1, k2, k3] + b^3 a[k3 + k4];
p[k1_, k2_, k3_, k4_, k5_] := 
  p[k1, k2, k3, k4, k5] = p[k1, k2, k3, k4] + b^4 a[k4 + k5];

and so on, where a is some function that is unimportant, and b is a constant.

Is there a one-liner for the "and so on" part, perhaps using SlotSequence? The issue is that ##n only allows you to start at positive integers, which makes things difficult (since for example in p[k1, k2, k3, k4, k5] = p[k1, k2, k3, k4] + a[k4 + k5] it uses a combination of the first four and the last two arguments). Might there be a simple way around this?

$\endgroup$
  • 4
    $\begingroup$ You also could use something like this: ClearAll[p]; p[x_] := p[x] = b^0*a[x]; p[fst___, x_, y_] := p[fst, x, y] = p[fst, x] + b^(Length[{fst}] + 1)*a[x + y]. $\endgroup$ – Leonid Shifrin Apr 15 '15 at 2:50
6
$\begingroup$

Here's a way using BlankNullSequence:

Clear[p];
p[k_] := p[k] = a[k]
pk : p[k0___, k1_, k2_] := pk = p[k0, k1] + b^Length[{k0, k1}] p[k1 + k2]

We can test this on an example:

p[k1, k2, k3, k4, k5]
(* a[k1] + b a[k1 + k2] + b^2 a[k2 + k3] + b^3 a[k3 + k4] + b^4 a[k4 + k5] *)

And then check Definition[p] to make sure the values were correctly memoized:

p[k1]=a[k1]
p[k1+k2]=a[k1+k2]
p[k2+k3]=a[k2+k3]
p[k3+k4]=a[k3+k4]
p[k4+k5]=a[k4+k5]
p[k1,k2]=a[k1]+b a[k1+k2]
p[k1,k2,k3]=a[k1]+b a[k1+k2]+b^2 a[k2+k3]
p[k1,k2,k3,k4]=a[k1]+b a[k1+k2]+b^2 a[k2+k3]+b^3 a[k3+k4]
p[k1,k2,k3,k4,k5]=a[k1]+b a[k1+k2]+b^2 a[k2+k3]+b^3 a[k3+k4]+b^4 a[k4+k5]
p[k_]:=p[k]=a[k]
pk:p[k0___,k1_,k2_]:=pk=p[k0,k1]+b^Length[{k0,k1}] p[k1+k2]

I personally like to define the base cases for recursive functions using patterns instead of If-statements, and since Mathematica has extremely fast pattern matching there isn't a performance hit.

So, we define the base case (p called with one element) first. This uses one method of memoization, where we duplicate the pattern (p[k_]) in the LHS of Set (p[k]).

This can be a little clumsy or error-prone for more complex memoizations, so I use another method in the second definition: giving the whole pattern a name (pk : _), and then just using that name in the assignment (pk = _).

As for the second pattern itself, we need to name the last two arguments (k1_ and k2_), since they are both referenced explicitly. However, the rest of the arguments don't need to be named individually, so we can match a sequence (k0___). We don't use BlankSequence (__), since we need to handle cases with only two arguments, where k0 will end up being just Sequence[].

After figuring out the arguments, it's simple to write the function. Just remember that you can't do something like Length[k0]: for p[a, b, c, d] that would end up Length[a, b]. You'd want Length[{k0}], which ends up Length[{a, b}].

$\endgroup$
  • $\begingroup$ And how is this any different in any non-trivial way from Leonid' s comment? $\endgroup$ – ciao Apr 15 '15 at 3:18
  • $\begingroup$ @rasher oops, didn't notice that comment ;;0_0 Guess it was posted while I was writing. The solutions themselves are totally identical, yeah... can I split the rep with him? What's procedure here? $\endgroup$ – 2012rcampion Apr 15 '15 at 3:34
  • 1
    $\begingroup$ It happens - done it myself. I delete to give commenter time to make it answer - particularly when an expert/regular, if that doesn't happen, fair game. $\endgroup$ – ciao Apr 15 '15 at 3:43
  • 3
    $\begingroup$ @rasher Comments are not supposed to be actual answers. But they can provide a light-weight way to answer or give hints. If someone takes a comment of someone else and posts this (or similar) as an answer, this is totally fine, I think. $\endgroup$ – Leonid Shifrin Apr 15 '15 at 10:48
3
$\begingroup$

Here's one way to go about it.

Clear[p];
p[k_] := p[k] = If[Length[k] > 1, 
  p[Drop[k, -1]] + b^(Length[k] - 1) a[k[[-2]] + k[[-1]]], a[First[k]]];

For example:

p[{k1, k2, k3, k4, k5}]

a[k1] + b a[k1 + k2] + b^2 a[k2 + k3] + b^3 a[k3 + k4] + b^4 a[k4 + k5]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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