 # Cyclic list via backtracking

Hello,

Suppose I have a predefined list such below, and i want to retrieve each member from the list non-deterministically:

``````new_list(List) :-
assert(predefined(List)).

list_item(X) :-
predefined(List),
member(X, List).
``````

Suppose I now want to cycle through the list,i.e. when the last item of the list was retrieved via backtracking, i want to start obtaining the first item again. So, list_item(X), backtracks infinitely, and without generation of excess memory.

Can this be accomplished?

thanks,

Dan

1 Like

How do you cycle the index … i guess one needs some kind of end-less recursion that “resets” the index, but that doesn’t increase the stack.

Perhaps tabling helps keep the stack constant

ok. i better look at this tomorrow morning with a fresh mind – right now it doesn’t register anymore To make this cyclic

``````list_item(X) :-
predefined(List),
append(List, Cyclic, Cyclic),
member(X, Cyclic).
``````

A more mundane solution is below. It should probably be called the more elegant one as it is easily understandable and doesn’t depend on the shady area of infinite data structures. The above one is to impress ``````loop_list(X, List) :-
member(X, List).
loop_list(X, List) :-
loop_list(X, List).
``````
1 Like

Thanks Jan,

The first solution is indeed a (shady) mystery How can something append to itself, and stay sane …

I guess, the second solution is “compiled” into a loop, through tail recursions.

Dan

By becoming cyclic The second clause is tail recursive, so the thing runs in constant memory.

I ran this code

``````loop_list(X, List) :-
member(X, List).
loop_list(X, List) :-
loop_list(X, List).
``````

using gtrace/0 and let it return many values. As it stared the loop again the call stack size increased by one, e.g. Is the stack size really growing? If so then how can this be constant memory?

i think tail recursive optimization is disabled during debug.

2 Likes

Hi

Jan has already shown how it can be done, but, just for the fun of it, you can also have a cyclic list without backtracking. Like this:

``````L = [1,2,3|L]
``````

Of course you can backtrack infinitely over this list with `member(X,L)`.

Happy hacking,
Volker

1 Like

thanks.

I also noticed this:

:-? append(, Cyclic, Cyclic).
Cyclic = [1|Cyclic].

That `append(, Cyclic, Cyclic)` is a little hard to read. You could make it more clear like this:

``````append(L, End, Cycl),
End = Cycl
``````

Bye
Volker

After trying it out a bit, i really like this structure.

L is essentially a pointer to itself, and hence the cyclicity.

I recall the notion of sets that contain themselves – there is a whole theory about it with alternative foundational axioms. But, for the purpose of creating a cyclic list that seems great.

Jan’s append is exactly equivalent to this.

Dan