Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Mathematica has had NestWhile and NestWhileList for some time. But, to date, it has not implemented a built-in FoldWhile or a FoldWhileList. So, since these constructs seem useful to me, I have tried to brew my own. Here are my current implementations. Anyone have suggestions on how either of these might be improved. I'd be particularly interested in a variant of FoldWhile that did not require as much memory as FoldWhileList.

 FoldWhileList[f_, init_, list_, test_, m_, max_] := 
 Block[{i = 0}, 
    NestWhileList[(i = i + 1; f[#, Part[list, i]]) &, init, test, m, max]]

and

 FoldWhile[f_, init_, list_, test_, m_, max_] := 
    Last[FoldWhileList[f, init, list, test, m, max]]
share|improve this question
    
Seth, regarding your comments: indeed, I did not implement the capability to use m most recent results. I this is really necessary, then your implementation is likely a way to go, since Fold can not be used to implement this. As to the complexity - I don't think most users have to reimplement it themselves - they could as well come to this page and pick whichever implementation they like the most :). –  Leonid Shifrin Feb 7 '13 at 8:40

3 Answers 3

Implementation

Here are my versions. I will start with FoldWhile:

Clear[dressInCtr];
dressInCtr[test_, max_] := 
   Module[{ctr = 0}, (++ctr <= max ) && test[##] &]

Clear[FoldWhile];
FoldWhile[f_, test_, start_, secargs_List, max_Integer] :=
   FoldWhile[f, dressInCtr[test, max], start, secargs];

FoldWhile[f_, test_, start_, secargs_List] :=
  Module[{last = start},
    Fold[
      If[test[##], last = f[##], Return[last, Fold]] &, 
      start, 
      secargs]];

The FoldWhileList is a bit more involved:

Clear[FoldWhileList];
FoldWhileList[f_, test_, start_, secargs_List, max_Integer] :=
   FoldWhileList[f, dressInCtr[test, max], start, secargs];
FoldWhileList[f_, test_, start_, secargs_List] :=
Module[{tag},
   If[# === {}, {start}, Prepend[First@#, start]] &@
    Reap[
      Fold[
        If[test[##], Sow[f[##],tag], Return[Null, Fold]] &, 
        start, 
        secargs], 
      _, #2 &][[2]]]

Examples

Here are some examples:

FoldWhileList[Plus,#2<5&,0,Range[30]]

(* {0,1,3,6,10}  *)

FoldWhileList[Plus,#2<5&,0,Range[30],3]

(* {0,1,3,6} *)

FoldWhile[Plus,#2<5&,0,Range[30]]

(* 10  *)

FoldWhile[Plus,#2<5&,0,Range[30],3]

(* 6 *)

Remarks

I chose to use Fold itself as an economical way to implement FoldWhile and FoldWhileList. It helped that the two-argument version of Return (undocumented) could be used here. I also found it simplest to implement the extended form with a fifth parameter giving maximal number of iterations, by dressing the test criteria in a closure, which is done via a closure generator function dressInCtr. This also seems to be a good illustration of the usefulness of closures.

share|improve this answer
    
Didn't know Return had a second argument, odd thing to leave out of the documentation. –  ssch Feb 5 '13 at 20:13
2  
@ssch Agree. This second argument business is explained very well in this excellent answer by Rojo. That answer deserves many more upvotes IMO. –  Leonid Shifrin Feb 5 '13 at 20:18
    
Got 6 upvotes on that answer today. Thanks ;) –  Rojo Feb 5 '13 at 22:08
    
Btw, making FoldWhileList using FoldList with a modified function that sows the result would be as efficient? –  Rojo Feb 5 '13 at 22:09
    
@Rojo Welcome :-). Re: as efficient: memory-wise, no, since Sow will have to store those intermediate results internally. This, plus the fact that I can make the code simpler, was my motivation to implement it separately. As for run-time efficiency, a bit less efficient too, but probably not much so. –  Leonid Shifrin Feb 5 '13 at 22:19
foldWhile[function_, check_, x_, list_, m_: Infinity] :=
 Module[{counter = 0, out, restart, newValue, result = x, 
   max = Min[m, Length@list]},
  Label[restart];
  ++counter;
  newValue = list[[counter]];
  If[! check[result, newValue] || counter >= max, Goto[out]];
  result = function[result, newValue];
  Goto[restart];
  Label[out];
  result
  ]

Another one

foldWhile[function_, check_, x_, list_, m_: Infinity] :=
 Module[{max = Min[m, Length@list]},
  (Composition @@ list~Take~max)[#][x] //. {
    res_[Except[#, next_][rest_]][val_] /; check[res, next] :> 
     function[val, res][rest][next],
    res_[_][val_] :> function[val, res]
    }
  ]

For both

foldWhileList[f_, test_, start_, rest___] := Module[{tag}, Reap[
    foldWhile[
     Sow[f@##, tag] &, test, Sow[start, tag], rest], tag][[-1, 1]]]
share|improve this answer
    
@Leonid, ironically, this beats yours for long lists that test out early. Probably you are making a copy of the list in your solution? –  Rojo Feb 6 '13 at 1:30
    
No time to benchmark now, but no, I don't make a copy, at least I don't see any obvious place where I do. Will look into that later. –  Leonid Shifrin Feb 6 '13 at 15:26
    
Please take a look at Seth's now deleted post further down. He had a comment for you. –  rm -rf Feb 7 '13 at 6:15
    
@rm-rf does it work for you? I just tried it with the 2 examples in Leonid's answer and it worked –  Rojo Feb 7 '13 at 11:53
    
Sorry, I haven't tried it yet... been a bit occupied with other things (I haven't fixed my zero rows removal answer either!) –  rm -rf Feb 7 '13 at 20:05

These are the first methods that came to mind. I'll have to leave comparing them to the other answers for later.

FoldWhile[f_, start_, rest_, test_] :=
 Module[{g},
   g[_, x_?test] := x;
   g[last_, _] := Return[last, Fold];
   Fold[# ~g~ f@## &, start, rest]
 ]

FoldWhile[Plus, 0, Range@100, # < 30 &]
28
FoldWhileList[f_, start_, rest_, test_] :=
 Module[{bag = Internal`Bag[start], g},
  g[x_?test] := (Internal`StuffBag[bag, x]; x);
  g[else_] := Return[Null, Fold];
  Fold[g @ f @ ## &, start, rest];
  Internal`BagPart[bag, All]
 ]

FoldWhileList[Plus, 0, Range@100, # < 30 &]
{0, 1, 3, 6, 10, 15, 21, 28}
share|improve this answer
    
I'm curious too as to how they all perform, but don't take my answer too seriously –  Rojo Feb 6 '13 at 9:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.