Searching from the end of a list in Mathematica

Question

Many algorithms (like the algorithm for finding the next permutation of a list in lexicographical order) involve finding the index of the last element in a list. However, I haven't been able to find a way to do this in Mathematica that isn't awkward. The most straightforward approach uses LengthWhile, but it means reversing the whole list, which is likely to be inefficient in cases where you know the element you want is near the end of the list and reversing the sense of the predicate:

findLastLengthWhile[list_, predicate_] :=
 (Length@list - LengthWhile[Reverse@list, ! predicate@# &]) /. (0 -> $Failed)

We could do an explicit, imperative loop with Do, but that winds up being a bit clunky, too. It would help if Return would actually return from a function instead of the Do block, but it doesn't, so you might as well use Break:

findLastDo[list_, pred_] :=
 Module[{k, result = $Failed},
  Do[
   If[pred@list[[k]], result = k; Break[]],
   {k, Length@list, 1, -1}];
  result]

Ultimately, I decided to iterate using tail-recursion, which means early termination is a little easier. Using the weird but useful #0 notation that lets anonymous functions call themselves, this becomes:

findLastRecursive[list_, pred_] :=
 With[{
   step =
    Which[
      #1 == 0, $Failed,
      pred@list[[#1]], #1,
      True, #0[#1 - 1]] &},
  step[Length@list]]

All of this seems too hard, though. Does anyone see a better way?

EDIT to add: Of course, my preferred solution has a bug which means it's broken on long lists because of $IterationLimit.

In[107]:= findLastRecursive[Range[10000], # > 10000 &]
$IterationLimit::itlim: Iteration limit of 4096 exceeded. 
Out[107]= (* gack omitted *)

You can fix this with Block:

findLastRecursive[list_, pred_] :=
 Block[{$IterationLimit = Infinity},
  With[{
    step =
     Which[
       #1 == 0, $Failed,
       pred@list[[#1]], #1,
       True, #0[#1 - 1]] &},
   step[Length@list]]]

$IterationLimit is not my favorite Mathematica feature.

Answer 1

Not really an answer, just a couple of variants on findLastDo.

(1) Actually Return can take an undocumented second argument telling what to return from.

In[74]:= findLastDo2[list_, pred_] := 
 Module[{k, result = $Failed}, 
  Do[If[pred@list[[k]], Return[k, Module]], {k, Length@list, 1, -1}];
  result]

In[75]:= findLastDo2[Range[25], # <= 22 &]
Out[75]= 22

(2) Better is to use Catch[...Throw...]

In[76]:= findLastDo3[list_, pred_] := 
 Catch[Module[{k, result = $Failed}, 
   Do[If[pred@list[[k]], Throw[k]], {k, Length@list, 1, -1}];
   result]]

In[77]:= findLastDo3[Range[25], # <= 22 &]
Out[77]= 22

Daniel Lichtblau

Answer 2

For the adventurous...

The following definitions define a wrapper expression reversed[...] that masquerades as a list object whose contents appear to be a reversed version of the wrapped list:

reversed[list_][[i_]] ^:= list[[-i]]
Take[reversed[list_], i_] ^:= Take[list, -i]
Length[reversed[list_]] ^:= Length[list]
Head[reversed[list_]] ^:= List

Sample use:

$list = Range[1000000];
Timing[LengthWhile[reversed[$list], # > 499500 &]]
(* {1.248, 500500} *)

Note that this method is slower than actually reversing the list...

Timing[LengthWhile[Reverse[$list], # > 499500 &]]
(* 0.468, 500500 *)

... but of course it uses much less memory.

I would not recommend this technique for general use as flaws in the masquerade can manifest themselves as subtle bugs. Consider: what other functions need to implemented to make the simulation perfect? The exhibited wrapper definitions are apparently good enough to fool LengthWhile and TakeWhile for simple cases, but other functions (particularly kernel built-ins) may not be so easily fooled. Overriding Head seems particularly fraught with peril.

Notwithstanding these drawbacks, this impersonation technique can sometimes be useful in controlled circumstances.