Determine whether reached end of an open list

Help!
1

I’d like an easy way to identify the end of a list, where the list might be closed, open or involve coroutining. If the list is open, it should be kept open. Example:

Lst = [a|Gotcha], freeze(Gotcha, Gotcha = [b,c|Tail]).

The end of Lst is Tail. Because of the freeze, == is insufficient, and unification would unintentionally close an open list.

I thought I was being clever in using:

\+ \+ Elem = []

… which is not tricked by Gotcha. But, false disapproves, so I’m back to questioning my understanding of reality.

Are mere mortals meant to use '$skip_list'(Length, List, Tail) (as seen in library), given its lack of documentation?

2

I was hoping someone else would chip in because Prolog lists confuse me. First note:

?- [1,X] =.. L.
L = ['[|]', 1, [X]].

?- [1|X] =.. L.
L = ['[|]', 1, X].

So what do you mean by an open list? I’ll assume the second and call it an an indefinite list, i.e., one that can be extended by binding X to a list (which may also be an indefinite list). You can make it a definite/closed list by walking to the end and binding the “tail” to a closed list, e.g., the empty list. A predicate which walks to the end of an indefinite list:

list_tail([_|T], Tail) :- 
	(var(T) -> Tail = T ; list_tail(T, Tail)).

e.g.,

?- list_tail([], T).
false.

?- list_tail([1,Z], T).
false.

?- L=[1,2|X], list_tail(L,Tail).
L = [1, 2|Tail],
X = Tail.

?- L=[1,2|X], list_tail(L,Tail), Tail=[3].
L = [1, 2, 3],
X = Tail, Tail = [3].

A predicate which constrains a term to be an indefinite list (forever):

indefinite([_|Tail]) :- 
	(var(Tail)
	 -> freeze(Tail, indefinite(Tail))
	 ;  indefinite(Tail)
	).

e.g.,

?- indefinite(L), L=[1,2|X], list_tail(L,Tail).
L = [1, 2|Tail],
X = Tail,
freeze(Tail, indefinite(Tail)).

?- indefinite(L), L=[1,2,X], list_tail(L,Tail).
false.

?- indefinite(L), L=[1,2|X], list_tail(L,[3,4|_]).
L = [1, 2, 3, 4|_A],
X = [3, 4|_A],
freeze(_A, indefinite(_A)).

Any help?

1 Like
3

It is just a matter of convention for readability, isn’t it ?

% ?- [a]==[a|[]].
%@ true.
% ?- [a,b]==[a|[b]].
%@ true.
% ?- [a,b,c]==[a|[b|[c|[]]]].
%@ true.

% ?- X=[a|b,c].
%@ ERROR: Syntax error: Unexpected comma or bar in rest of list
%@ ERROR: X=[a|
%@ ERROR: ** here **
%@ ERROR: b,c] . 

% ?- X=[a|(b,c)].
%@ X = [a|(b, c)].

I don’t know how to explain this convention in a formal way.

4

This is wrong, with my Gotcha example, because Gotcha is var but involves freeze/2.

\+ \+ Elem = [] performs a dry run of unifying with [], so doesn’t get Gotcha’d. It seems correct.

5

So I got a bit sidetracked by the title: "Determine whether reached end of an open list ".

To also permit a closed list tail (which is always [] for a proper list):

list_tail([],[]).	
list_tail([_|T], Tail) :- 
	((var(T);(T==[])) -> Tail = T ; list_tail(T, Tail)).

Now:

?- list_tail([],T).
T = [].

?- list_tail([1],T).
T = [].

?- Lst = [a|Gotcha], list_tail(Lst,LT1), freeze(Gotcha, Gotcha = [b,c|Tail]), list_tail(Lst,LT2), Gotcha=[X|Y], list_tail(Lst,LT3).
Lst = [a, b, c|LT3],
Gotcha = LT1, LT1 = LT2, LT2 = [b, c|LT3],
Tail = LT3,
X = b,
Y = [c|LT3].

Now what do you want/expect to happen under what circumstances?

I think this is incorrect; == doesn’t unify anything.

6

You claim unification is insufficient but I don’t see why. My understanding is if you insert this code:

Gotcha = []

This will trigger the freeze, which will attempt to put Gotcha = [b,c|Tail], and fail.

So then you go Gotcha = [b|Remainder]
and this triggers [b|Remainder] = [b,c|Tail]
resulting in Remainder = [c|Tail].

This should work.

7

To clarify, I meant “and unification (i.e. =) …”

8

I suppose the question is, which is better:

(var(T) ; T==[])

\+ \+ T = []
9

Given your use of freeze, the first case answers that you have not bound any further yet, but does not take into account the pending freeze.

The second case does take into account freeze, and tells if you are allowed to terminate the list without any more entries.

T = [] on the third hand attempts to close the list for you, and will fail if freeze fails. In most cases, that is how I would write my code. I usually see no reason to ask “can the list end here?” if I don’t intend to end the list here.

Okay here’s a case: Suppose you have a generator somewhere else in your program that’s asynchronous to your current function which is a consumer. In that case, you don’t want to modify the open list at all. You might want code like

var(T) -> data_hasnt_arrived_yet
; T == [] -> end_of_file_reached
; T = [A|NextT], process(A)
10

T = [] would unwantedly close an open list.

11

My use-case is recursion - Reaching end of list in prolog - Stack Overflow

I’m iterating through a list, using freeze/2, checking the list contents in both directions.

I don’t think it would be appropriate for my iteration code to present the 2 possibilities, for each list element, of closing the list or not.

12

Looking there, Volodymyr Gubarkov has a fine answer. I completely don’t understand why you would want to introduce freeze. The question doesn’t have open lists.

13

I’m thinking of a general case. The list elements could become instantiated at a later point. Hence the use of coroutining - to wait for that later point, and perform the checks when able.

14 
check(L) :- 
    freeze(L, check_1(L).

check_1([]).
check_1([A | L]) :-
    freeze(L, check_2(A, L).
check_2(A, []).
check_2(A, [B|L]) :-
     when(ground(A-B), A =< B),
     freeze(L, check_2(B, L)).

Not tested, but I think you get the idea. Notice check_2 will compare A and B when both are ground, and will check L when it’s no longer a var, so it is asynchronous, not sequential, if you as the user set the list in some weird order.

15

However:

check(L), L = [X,_|T], T = [_,Y|T2], X = 2, Y = 1.

… should fail, because X should be compared to Y at that point, in a way which doesn’t kill the performance. My code does that… and then gets called too complicated :joy:

16

Use CLP(int) and instead of checking if A and B are ground, use that system’s < constraint. I think it will resolve (3 < A, A < 2) to failure.

And yes, your code is too complicated, particularly because OP wasn’t asking for just-in-time solving, but also, I think it can be done more simply.

17

I created a general solution, which works on not just integers.

1 Like