# FoldWhile and FoldWhileList

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]]

-
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

### 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.

-
Didn't know Return had a second argument, odd thing to leave out of the documentation. – ssch Feb 5 '13 at 20:13
@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]]]

-
@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. – R. M. 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!) – R. M. 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 = InternalBag[start], g},
g[x_?test] := (InternalStuffBag[bag, x]; x);
g[else_] := Return[Null, Fold];
Fold[g @ f @ ## &, start, rest];
InternalBagPart[bag, All]
]

FoldWhileList[Plus, 0, Range@100, # < 30 &]

{0, 1, 3, 6, 10, 15, 21, 28}
`
-
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