# Combining memoization and SlotSequence

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?

• 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]. – Leonid Shifrin Apr 15 '15 at 2:50

## 2 Answers

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}].

• And how is this any different in any non-trivial way from Leonid' s comment? – ciao Apr 15 '15 at 3:18
• @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? – 2012rcampion Apr 15 '15 at 3:34
• 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. – ciao Apr 15 '15 at 3:43
• @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. – Leonid Shifrin Apr 15 '15 at 10:48

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]