Solution 1
A solution using Sow
and Reap
:
Reap[
Module[
{c = Infinity},
Scan[
If[#[[1]] < c, c = #[[1]]; Sow@#] &,
l
]
]
][[2, 1]]
This one keeps track of the current maximum through the variable c
, and uses Sow
and Reap
to collect the data.
Solution 2
Another one, this time without Module
:
Reap[
MapThread[
If[#1[[1]] == #2, Sow@#1] &,
{
l,
Rest@FoldList[Min[#, #2[[1]]] &, Infinity, l]
}
]
][[2, 1]]
This one creates a list of the current minimum at each position using FoldList
, and uses this list together with the original one in MapThread
Solution 3
And a third, based on the previous one:
Select[
{
l,
Rest@FoldList[Min[#, #2[[1]]] &, Infinity, l]
}\[Transpose]
, Apply[#1[[1]] == #2 &]
][[All, 1]]
Pretty similar to the previous one, but we put the lists together using Transpose{l1,l2}
, and filter using Select
Solution 4
Reap[
Fold[
If[#1 > #2[[1]], Sow@#2; #2[[1]], #1] &,
Infinity,
l
]
][[2, 1]]
This is very similar to the first one, but instead of a local variable c
, this one uses Fold
to pass the current minimum along.
Timings
I attempted to perform some benchmarking, using randomly generated data:
data[n_] := Table[{RandomInteger[n], Indexed[data, i]}, {i, n}]
The results are the following:

Delete[l, Position[Sign[Differences[l[[All, 1]]]], 1] + 1]
? $\endgroup${{6, data1}, {8, data2}, {7, data3},...
$\endgroup${{6, data1}, {5, data4}, {1, data7}}
also satisfies "the resulting list has the value property of its elements sorted", but I assume it's not a valid answer. $\endgroup$