Prolog: How "length(+,-)" delete unassigned tail of the list keeping the list?

Question

Again a Prolog beginner :-}

I build up a list element by element using

(1) member(NewElement,ListToBeFilled). in a repeating call,

(2)

ListToBeFilled = [NewElement|TmpListToBeFilled].

in a recursive call like

something(...,TmpListToBeFilled).

A concrete example of (2)

catch_all_nth1(List, AllNth, Counter, Result) :-
   [H|T] = List,
   NewCounter is Counter + 1,
   (
      0 is Counter mod AllNth
   ->
      Result = [H|Result1]      
   ;
      Result = Result1  
   ),
   catch_all_nth1(T,AllNth,NewCounter,Result1),
   !.
catch_all_nth1([], _, _, _).

As result I get a list which looks like

[E1, E2, E3, ..., Elast | _G12321].

Of course, the Tail is a Variable. [btw: are there better method to fill up the list, directly avoiding the "unassigned tail"?]

I was now looking for a simple method to eliminate the "unassigned tail".

I found: Delete an unassigned member in list there it is proposed to use:

exclude(var, ListWithVar, ListWithoutVar),!,

[Found this too, but did not help as I do not want a dummy element at the end Prolog list has uninstantiated tail, need to get rid of it ]

What I noticed is that using length\2 eliminate the "unassigned tail", too, and in addtion the same List remains.

My Question is: How does it work? I would like to use the mechanism to eliminate the unassigned tail without using a new variable... [in SWI Prolog 'till now I did not get the debugger entering length() ?!]

The example:

Z=['a','b','c' | Y],
X = Z,
write(' X '),write(X),nl,
length(X,Tmp),
write(' X '),write(X),nl.

13 ?- test(X).
X [a,b,c|_G3453]
X [a,b,c]
X = [a, b, c] .

I thought X, once initialized can not be changed anymore and you need a new variable like in exclude(var, ListWithVar, ListWithoutVar).

Would be happy if someone explain the trick to me...

Thanks :-)

Answer 1

I think this should do it:

% case 1: end of list reached, replace final var with empty list
close_open_list(Uninstantiated_Var) :- 
    var(Uninstantiated_Var), !,
    Uninstantiated_Var = '[]'.

% case 2: not the end, recurse
close_open_list([_|Tail]) :- 
    close_open_list(Tail).


?- X=[1,2,3|_], close_open_list(X).
X = [1, 2, 3].

Note that only variable X is used.. it simply recurses through the list until it hits the var at the end, replaces it with an empty list, which closes it. X is then available as a regular 'closed' list.

Edit: once a list element has been assigned to something specific, it cannot be changed. But the list itself can be appended to, when constructed as an open list ie. with |_ at the end. Open lists are a great way to build up list elements without needing new variables. eg.

X=[1,2,3|_], memberchk(4, X), memberchk(5,X).
X = [1, 2, 3, 4, 5|_G378304]

In the example above, memberchk tries tries to make '4', then '5' members of the list, which it succeeds in doing by inserting them into the free variable at the end in each case.

Then when you're done, just close it.

Answer 2

You're right about the strange behaviour: it's due to the ability of length/2 when called with unbound arguments

The predicate is non-deterministic, producing lists of increasing length if List is a partial list and Int is unbound.

example:

?- length([a,b,c|X],N).
X = [],
N = 3 ;
X = [_G16],
N = 4 ;
X = [_G16, _G19],
N = 5 ;
...

For your 'applicative' code, this tiny correction should be sufficient. Change the base recursion clause to

catch_all_nth1([], _, _, []).

here are the results before

4 ?- catch_all_nth1([a,b,c,d],2,1,R).
R = [b, d|_G75].

and after the correction:

5 ?- catch_all_nth1([a,b,c,d],2,1,R).
R = [b, d].

But I would suggest instead to use some of better know methods that Prolog provide us: like findall/3:

?- findall(E, (nth1(I,[a,b,c,d],E), I mod 2 =:= 0), L).
L = [b, d].