Monotonify (list-munging) without For loop

Question

For while or While loops in Mathematica code, always make me feel a little dirty, but I am confused trying to make some kind of list processing all functionally similar and resorted to this:

(* # Given a list of {x,y} pairs, transform the data as follows: every time # there a decrease in y-value from one datapoint to the next, say {x1,Y} # followed by {x2,y}, add Y to the value of every datapoint on or after x2. *) monotonify[data_] := Module[{data0, i, offset = 0}, data0 = data; For[i = 2, i <= Length[data], i++, If[data[[i-1,2]] > data[[i,2]], offset += data[[i-1,2]]]; data0[[i]] += {0,offset}]; data0] 

(Think of the y values ​​as the odometer readings, where sometimes the odometer occasionally shows a reset - obviously because the value decreases, the odometers shouldn't. Therefore, we will convert the readings by adding the last known value before each reset to all future values.)

How could you write monotonation in a nice functional style?

(The fact that I don’t think the above loop cycle works fine is probably a mild form of OCD.)

Answer 1

OK, now I have corrected my approach to working with inputs, as was originally requested.

Start with a sample dataset:

 dataset = {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 0}, {g, 4}, {h,5}, {i, 6}, {j, 7}, {k, 4}, {l, 7}, {m, 8}, {n, 9}, {o, 0}, {p,2}, {q, 3}}; 

Take the transpose:

 trDataset = Transpose[dataset]; 

The following function only works with Y values:

 trDataset[[2]] = FoldList[Plus, dataset[[1, 2]], Map[Max[#, 0] &, Differences[dataset[[All, 2]]]]] 

Cancel transpose:

 dataset = Transpose[trDataset] 

and exit now

 {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 5}, {g, 9}, {h, 10}, {i, 11}, {j, 12}, {k, 12}, {l, 15}, {m, 16}, {n, 17}, {o, 17}, {p, 19}, {q, 20}} 

I still have not tested the performance of this solution.

EDIT: Okay, here is the basics of the fix, I'll leave all the work to you @dreeves. This version of monotonify only works on a list of numbers, I did not include it in my previous sentence to work with your inputs.

 monotonify[series_] := Split[series, Less] //. {a___, x_List, y_List, z___} /; Last[x] > First[y] -> {a, x, y + Last[x], z} // Flatten 

EDIT 2: Another function that works with a list of numbers. This is much faster than my previous attempt.

 monotonify[series_] := Accumulate[Flatten[Map[Flatten[{#[[1]], Differences[#]}] &, Split[series, Less]]]] 

Answer 2

Here is another solution:

 Module[{corr, lasts}, lasts = data[[All, 2]]; corr = Prepend[Accumulate[MapThread[If[#1 > #2, #1, 0] &, {Most[lasts], Rest[lasts]}]], 0]; Transpose[{data[[All, 1]], lasts + corr}]] 

It calculates a correction vector, which is then added to the y values ​​of the data data points.

Answer 3

As soon as the glove disappeared, I could not try it, but I think the version of the For loop is simpler:

 mon00[{prev_,offset_}, next_] := {next, offset + If[prev > next, prev, 0]} monotonify0[list_] := list + Rest[FoldList[mon00, {-Infinity,0}, list]][[All,2]] monotonify[data_] := Transpose@ {#1, monotonify0[#2]}& @@ Transpose@data 

The idea is to write a helper function that does this only for a simple list of y values, and then use a bidirectional idiom to work with only the second data column.

Useful link for idioms with two transpositions

To convert a specific column to a matrix, for example, replacing each x value in column 2 of a four-column matrix with transformElement [x]:

 {#1, transformElement[#2], #3, #4}& @@@ matrix 

If you need to convert a column with a function that takes the entire column as a list, use the following idiom:

 Transpose @ {#1, transformList[#2], #3, #4}& @@ Tranpose@matrix 

Answer 4

I did this using mostly Split , Flatten and Accumulate . I'm not sure that the end result is easier to understand than the For loop, but it should be nice and fast, if that matters.

 monotonize[list_] := With[{splits = Split[list, LessEqual]}, With[{diffs = Most[Last /@ splits] - Rest[First /@ splits]}, Flatten[ MapThread[Plus, {Accumulate[Prepend[diffs, 0]], splits}], 1]]]; monotonizeSecond[list_] := With[{firsts = First /@ list, lasts = Last /@ list}, Transpose[{firsts, monotonize@lasts }]]; 

I think abundant use for With makes it a little clearer than a solution that relied more on anonymous woulld functions. Also, monotonize looks like a thing that might be useful on "undecorated" lists, so I broke it up as a separate function.

Answer 5

In essence, this challenges the fact that most of the functional operators in Mathematica work one list item at a time. This is not the only option, however, these functions could be configured to accept two adjacent list items at a time; this hypothetical function would make it trivial to obtain the desired result.

Instead of transforming a function, we can easily transform the data using a section.

 Clear[monotonify]; monotonify[data_] := Transpose[{data[[All, 1]], Rest@FoldList [ If[#2[[1]] < #2[[2]], #1 + #2[[2]] - #2[[1]], #1 + #2[[2]]] &, 0, Partition[data[[All, 2]], 2, 1, {2, -1}, 0]]}] 

In this version, I refactor to add a helper function to understand how a folded function works, but the math also does not optimize it.

 Clear[monotonify, m00]; m00[acc_, {prev_, next_}] := If[prev < next, acc + next - prev, acc + next] monotonify[data_] := Transpose[{data[[All, 1]], Rest@FoldList [m00, 0, Partition[data[[All, 2]], 2, 1, {2, -1}, 0]]}] 

edit: forgot some {}