37
$\begingroup$

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

Note: These functions were introduced as built-ins in Version 12.2

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 :). $\endgroup$ Commented Feb 7, 2013 at 8:40
  • $\begingroup$ These seem still to be missing. Is there a ready explanation of why? $\endgroup$ Commented Sep 9, 2017 at 5:22

4 Answers 4

Reset to default
27
$\begingroup$

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.

Improve this answer
$\endgroup$
16
  • $\begingroup$ Didn't know Return had a second argument, odd thing to leave out of the documentation. $\endgroup$ Commented Feb 5, 2013 at 20:13
  • 2
    $\begingroup$ @ssch Agree. This second argument business is explained very well in this excellent answer by Rojo. That answer deserves many more upvotes IMO. $\endgroup$ Commented Feb 5, 2013 at 20:18
  • $\begingroup$ Got 6 upvotes on that answer today. Thanks ;) $\endgroup$ Commented Feb 5, 2013 at 22:08
  • $\begingroup$ Btw, making FoldWhileList using FoldList with a modified function that sows the result would be as efficient? $\endgroup$ Commented Feb 5, 2013 at 22:09
  • $\begingroup$ @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. $\endgroup$ Commented Feb 5, 2013 at 22:19
8
$\begingroup$

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}
Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm curious too as to how they all perform, but don't take my answer too seriously $\endgroup$ Commented Feb 6, 2013 at 9:23
7
$\begingroup$

Just FYI, Mathematica 12.2 introduces FoldWhile and FoldWhileList with the intended usages.

Improve this answer
$\endgroup$
6
$\begingroup$ 
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]]]
Improve this answer
$\endgroup$
5
  • $\begingroup$ @Leonid, ironically, this beats yours for long lists that test out early. Probably you are making a copy of the list in your solution? $\endgroup$ Commented Feb 6, 2013 at 1:30
  • $\begingroup$ 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. $\endgroup$ Commented Feb 6, 2013 at 15:26
  • $\begingroup$ Please take a look at Seth's now deleted post further down. He had a comment for you. $\endgroup$ Commented Feb 7, 2013 at 6:15
  • $\begingroup$ @rm-rf does it work for you? I just tried it with the 2 examples in Leonid's answer and it worked $\endgroup$ Commented Feb 7, 2013 at 11:53
  • $\begingroup$ Sorry, I haven't tried it yet... been a bit occupied with other things (I haven't fixed my zero rows removal answer either!) $\endgroup$ Commented Feb 7, 2013 at 20:05

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.