<p>You are touching on several extremely interesting aspects of Prolog, each well worth <em>several</em> separate questions on its own. I will provide a high-level answer to your actual questions, and hope that you post follow-up questions on the points that are most interesting to you.</p>

<p>First, I will trim down the fragment to its essence:</p>

<pre>
essence(N) :-
        foldl(essence_(N), [2|Back], Back, _).

essence_(N, X0, Back, Rest) :-
        (   X0 #&lt; N ->
            X1 #= X0 + 1,
            Back = [X1|Rest]
        ;   Back = []
        ).
</pre>

<p>Note that this prevents the creation of extremely large integers, so that we can really study the memory behaviour of this pattern.</p>

<p>To your first question: <strong>Yes</strong>, this runs in <strong>O(1)</strong> space (assuming constant space for arising integers).</p>

<p><em>Why?</em> Because although you continuously create lists in <code>Back = [X1|Rest]</code>, these lists can all be readily <strong>garbage&nbsp;collected</strong> because you are not referencing them anywhere.</p>

<p>To test memory aspects of your program, consider for example the following query, and limit the global stack of your Prolog system so that you can quickly detect growing memory by running out of (global) stack:</p>

<pre>
?- length(_, E),
   N #= 2^E,
   portray_clause(N),
   essence(N),
   false.
</pre>

<p>This yields:</p>

<pre>
1.
2.
...
8388608.
16777216.
etc.
</pre>

<p>It would be <strong>completely</strong> different if you <em>referenced</em> the list somewhere. For example:</p>

<pre>
essence(N) :-
        foldl(essence_(N), [2|Back], Back, _),
        <b>Back = []</b>.
</pre>

<p>With this very small change, the above query yields:</p>

<pre>
?- length(_, E),
   N #= 2^E,
   portray_clause(N),
   essence(N),
   false.
1.
2.
...
1048576.
<b>ERROR: Out of global stack</b>
</pre>

<p>Thus, whether a term is referenced somewhere can significantly influence the memory requirements of your program. This sounds quite frightening, but really is hardly an issue in practice: You either need the term, in which case you need to represent it in memory anyway, or you don't need the term, in which case it is simply no longer referenced in your program and becomes amenable to garbage collection. In fact, the amazing thing is rather that GC works so well in Prolog also for quite complex programs that not much needs to be said about it in many situations. </p>

<hr>

<p>On to your second question: Clearly, using <code>(-&gt;)/2</code> is almost always highly problematic in that it limits you to a particular direction of use, destroying the generality we expect from logical relations.</p>

<p>There are several solutions for this. If your CLP(FD) system supports <code>zcompare/3</code> or a similar feature, you can write <code>essence_/3</code> as follows:</p>

<pre>
essence_(N, X0, Back, Rest) :-
        zcompare(C, X0, N),
        closing(C, X0, Back, Rest).

closing(&lt;, X0, [X1|Rest], Rest) :- X1 #= X0 + 1.
closing(=, _, [], _).
</pre>

<p>Another very nice meta-predicate called <strong><code>if_/3</code></strong> was recently introduced in <a href="https://arxiv.org/abs/1607.01590" rel="nofollow"><strong>Indexing dif/2</strong></a> by Ulrich Neumerkel and Stefan Kral. I leave implementing this with <code>if_/3</code> as a very worthwhile and instructive exercise. Discussing this is <em>well worth its own question</em>!</p>

<hr>

<p>On to the third question: How do states with DCGs relate to this? DCG notation is definitely useful if you want to pass around a global state to several predicates, where only a few of them need to access or modify the state, and most of them simply pass the state through. This is completely analogous to <strong>monads</strong> in Haskell.</p>

<p>The "normal" Prolog solution would be to extend each predicate with 2&nbsp;arguments to describe the relation between the state before the call of the predicate, and the state after it. DCG notation lets you avoid this hassle.</p>

<p>Importantly, using DCG notation, you can copy imperative algorithms almost verbatim to Prolog, without the hassle of introducing many auxiliary arguments, even if you need global states. As an example for this, consider a fragment of Tarjan's <a href="https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm" rel="nofollow"><strong>strongly connected components</strong></a> algorithm in imperative terms:</p>

<pre>
  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)
</pre>

<p>This clearly makes use of a global <strong>stack</strong> and <strong>index</strong>, which ordinarily would become new arguments that you need to pass around in <em>all</em> your predicates. Not so with DCG notation! For the moment, assume that the global entities are simply easily accessible, and so you can code the whole fragment in Prolog as:</p>

<pre>
scc_(V) --&gt;
        vindex_is_index(V),
        vlowlink_is_index(V),
        index_plus_one,
        s_push(V),
</pre>

<p><em>This is a very good candidate for its own question</em>, so consider this a teaser.</p>

<hr>

<p>At last, I have a general remark: In my view, we are only <em>at the beginning</em> of finding a series of very powerful and general meta-predicates, and the solution space is still largely <em>unexplored</em>. <code>call/N</code>, <code>maplist/[3,4]</code>, <code>foldl/4</code> and other meta-predicates are definitely a good start. <code>if_/3</code> has the potential to combine good performance with the generality we expect from Prolog predicates.</p>
Fold over a partial list
<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>