title: Fold over a partial list
body: <p>This is a question provoked by an already deleted answer to <a href="https://stackoverflow.com/questions/39462366/how-can-i-determine-that-all-given-coordinates-of-matrix-are-connected">this question</a>. The issue could be summarized as follows:</p>
  
  <blockquote>
    <p>Is it possible to fold over a list, with the tail of the list generated while folding?</p>
  </blockquote>
  
  <p>Here is what I mean. Say I want to calculate the factorial (this is a silly example but it is just for demonstration), and decide to do it like this:</p>
  
  <pre><code>fac_a(N, F) :-
          must_be(nonneg, N),
          (       N =&lt; 1
          -&gt;      F = 1
          ;       numlist(2, N, [H|T]),
                  foldl(multiplication, T, H, F)
          ).
  
  multiplication(X, Y, Z) :-
          Z is Y * X.
  </code></pre>
  
  <p>Here, I need to generate the list that I give to <code>foldl</code>. However, I could do the same in constant memory (without generating the list and without using <code>foldl</code>):</p>
  
  <pre><code>fac_b(N, F) :-
          must_be(nonneg, N),
          (       N =&lt; 1
          -&gt;      F = 1
          ;       fac_b_1(2, N, 2, F)
          ).
  
  fac_b_1(X, N, Acc, F) :-
          (       X &lt; N
          -&gt;      succ(X, X1),
                  Acc1 is X1 * Acc,
                  fac_b_1(X1, N, Acc1, F)
          ;       Acc = F
          ).
  </code></pre>
  
  <p>The point here is that unlike the solution that uses <code>foldl</code>, this uses constant memory: no need for generating a list with all values!</p>
  
  <p>Calculating a factorial is not the best example, but it is easier to follow for the stupidity that comes next.</p>
  
  <p>Let's say that I am really afraid of loops (and recursion), and insist on calculating the factorial using a fold. I still would need a list, though. So here is what I might try:</p>
  
  <pre><code>fac_c(N, F) :-
          must_be(nonneg, N),
          (       N =&lt; 1
          -&gt;      F = 1
          ;       foldl(fac_foldl(N), [2|Back], 2-Back, F-[])
          ).
  
  fac_foldl(N, X, Acc-Back, F-Rest) :-
          (       X &lt; N
          -&gt;      succ(X, X1),
                  F is Acc * X1,
                  Back = [X1|Rest]
          ;       Acc = F,
                  Back = []
          ).
  </code></pre>
  
  <p>To my surprise, this works as intended. I can "seed" the fold with an initial value at the head of a partial list, and keep on adding the next element as I consume the current head. The definition of <code>fac_foldl/4</code> is almost identical to the definition of <code>fac_b_1/4</code> above: the only difference is that the state is maintained differently. My assumption here is that this should use constant memory: <strong>is that assumption wrong?</strong></p>
  
  <p>I know this is silly, but it could however be useful for folding over a list that cannot be known when the fold starts. In the original question we had to find a connected region, given a list of x-y coordinates. It is not enough to fold over the list of x-y coordinates once (you can however <a href="https://en.wikipedia.org/wiki/Connected-component_labeling#Two-pass" rel="nofollow noreferrer">do it in two passes</a>; note that there is at least <a href="http://www.sciencedirect.com/science/article/pii/S1077314202000309" rel="nofollow noreferrer">one better way to do it</a>, referenced in the same Wikipedia article, but this also uses multiple passes; altogether, the multiple-pass algorithms assume constant-time access to neighboring pixels!).</p>
  
  <p>My <a href="https://stackoverflow.com/a/39463442/1812457">own solution to the original "regions" question</a> looks something like this:</p>
  
  <pre><code>set_region_rest([A|As], Region, Rest) :-
          sort([A|As], [B|Bs]),
          open_set_closed_rest([B], Bs, Region0, Rest),
          sort(Region0, Region).
  
  open_set_closed_rest([], Rest, [], Rest).
  open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :-
          X0 is X-1, X1 is X + 1,
          Y0 is Y-1, Y1 is Y + 1,
          ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
          append(New, As, Open),
          open_set_closed_rest(Open, Set0, Closed0, Rest).
  </code></pre>
  
  <p>Using the same "technique" as above, we can twist this into a fold:</p>
  
  <pre><code>set_region_rest_foldl([A|As], Region, Rest) :-
          sort([A|As], [B|Bs]),
          foldl(region_foldl, [B|Back],
                              closed_rest(Region0, Bs)-Back,
                              closed_rest([], Rest)-[]),
          !,
          sort(Region0, Region).
  
  region_foldl(X-Y,
               closed_rest([X-Y|Closed0], Set)-Back,
               closed_rest(Closed0, Set0)-Back0) :-
          X0 is X-1, X1 is X + 1,
          Y0 is Y-1, Y1 is Y + 1,
          ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
          append(New, Back0, Back).
  </code></pre>
  
  <p>This also "works". The fold leaves behind a choice point, because I haven't articulated the end condition as in <code>fac_foldl/4</code> above, so I need a cut right after it (ugly).</p>
  
  <h2>The Questions</h2>
  
  <ul>
  <li>Is there a clean way of closing the list and removing the cut? In the factorial example, we know when to stop because we have additional information; however, in the second example, how do we notice that the back of the list should be the empty list?</li>
  <li>Is there a hidden problem I am missing?</li>
  <li>This looks like its somehow similar to the Implicit State with DCGs, but I have to admit I never quite got how that works; are these connected?</li>
  </ul>