Cyclic list via backtracking

Help!
1

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
3

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

4

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

5

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 :slight_smile:

loop_list(X, List) :-
    member(X, List).
loop_list(X, List) :-
    loop_list(X, List).
1 Like
6

Thanks Jan,

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

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

Dan

7

By becoming cyclic :slight_smile:

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

8

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.

image

Is the stack size really growing? If so then how can this be constant memory?

9

i think tail recursive optimization is disabled during debug.

2 Likes
10

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
11

thanks.

I also noticed this:

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

12

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

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

Bye
Volker

13

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