Accumulate second elements in sublist

Question

I want to accumulate the second elements in each sublist identified by its first element.

{
  {{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}}, 
  {{2, 1}, {3, 1}},
  {{7, 1}}, {{2, 3}}, {{3, 2}},
  {{2, 1}, {5, 1}},
  {{11, 1}},
  {{2, 2}, {3, 1}},
  {{13, 1}},
  {{2, 1}, {7, 1}},
  {{3, 1}, {5, 1}},
  {{2, 4}}, {{17, 1}},
  {{2, 1}, {3, 2}}
 }

For the first eight elements in my list

{{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}}, {{2, 1}, {3, 1}}, {{7, 1}}, {{2, 3}}}, ...

the desired result is

{{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 3}}, {{5, 1}}, {{2, 4}, {3, 2}}, {{7, 1}}, {2, 7}}}, ...

In the result, the first element of each sublist will be the identification element, and the second element is just how much of the first element there are upto any given postition of the list

So for the sixth position in the list, {{2, 1}, {3, 1}}, the result would be {{2, 4}, {3, 2}}, because by that time in the list there will be an accumilation of 4 'twos' and 2 'threes'.

Answer 1

Similar in idea to Hassler Thurston's, different in style:

acc[l_List] := Module[{reg, f},
  reg[_] = 0; (* register reg[x] stores the current total for index x *)
  SetAttributes[f, Listable];
  {f[x_], f[a_]} ^:= {x, reg[x] = reg[x] + a};
  f[l]
  ]

OP's example:

list = {{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 2}}, {{5, 1}}, {{2, 1}, {3,
      1}}, {{7, 1}}, {{2, 3}}, {{3, 2}}, {{2, 1}, {5, 1}}, {{11, 
     1}}, {{2, 2}, {3, 1}}, {{13, 1}}, {{2, 1}, {7, 1}}, {{3, 1}, {5, 
     1}}, {{2, 4}}, {{17, 1}}, {{2, 1}, {3, 2}}};

acc[list]
(*
  {{{1, 1}}, {{2, 1}}, {{3, 1}}, {{2, 3}}, {{5, 1}}, {{2, 4}, {3, 2}},
    {{7, 1}}, {{2, 7}}, {{3, 4}}, {{2, 8}, {5, 2}}, {{11, 1}},
    {{2, 10}, {3, 5}}, {{13, 1}}, {{2, 11}, {7, 2}}, {{3, 6}, {5, 3}},
    {{2, 15}}, {{17, 1}}, {{2, 16}, {3, 8}}}
*)

Answer 2

For each "first element", keep a count of its accumulation:

SecondLevelAccumulation[list_] := Module[{counts, replace},
    counts = {};
    replace[tuple_] := Module[{},
        (* If we've never seen a "first element", initialize its count to 0 *)
        If[! MemberQ[counts[[All, 1]], tuple[[1]]],
            AppendTo[counts, tuple[[1]] -> 0]];
        (* Then update the count to reflect the tuple's second element *)
        counts = counts /. {(tuple[[1]] -> a_) :> (tuple[[1]] -> a + tuple[[2]])};
        (* Finally, replace the second element of the given tuple to its accumulation *)
        {tuple[[1]], tuple[[1]]/.counts}
    ];
    (* As a last step, map the replace function to the original list at level 2 *)
    Map[replace, list, {2}]
]

Result:

Answer 3

Michael posted a good method but it uses the Listable Attribute and UpSetDelayed (^:=) which are both fairly advanced concepts. Since I know that you are in the process of learning Mathematica let me show you that these methods are simply not necessary here.

I too will use the simple counter construct I often do^(1),(2) and which is discussed in More efficient way of generating list of occurrence counts?

Fundamentally I shall be using a pattern and I shall need to restrict it⁽³⁾⁽⁴⁾; I shall show both levelspec and purely pattern based approaches.

For all examples I have assigned your input expression to data.

levelspec in Replace:

Module[{count},
  count[_] = 0;
  Replace[data, {i_, n_} :> {i, count[i] += n}, {2}]
]

Pattern only in ReplaceAll:

Module[{count},
  count[_] = 0;
  data /. {i_, n_Integer} :> {i, count[i] += n}
]

In addition to these examples you may find it interesting that the counter need not be localized, e.g. with Module, should you actually want to apply it globally:

count[_] = 0;
fn = # /. {i_, n_Integer} :> {i, count[i] += n} &;

Now:

fn @ {{1, 1}, {2, 1}, {3, 1}}
fn @ {{3, 4}, {5, 1}}
fn @ {{2, 2}, {3, 1}}

{{1, 1}, {2, 1}, {3, 1}}

{{3, 5}, {5, 1}}

{{2, 3}, {3, 6}}

To resent the counter you can use this:

ClearAll[count]; count[_] = 0;