Just wanted to define the \mathbb{Q} subset of the Cantor Set via Prolog:
cantor_set(L) :- \+ member(1, L).
member/2 seems to loop for cyclic lists. This query works:
?- L = [2,0,1|L], cantor_set(L).
false.
But this query doesn’t work, it should show true:
?- L = [0,2,0|L], cantor_set(L).
%%% hangs
Is there a standard way to make it non-looping?
Doesn’t sort/2 help here?
cantor_set(L) :-
sort(L, S),
\+ member(1, S).
The other option would be to have a member/2 that detects cycles….
Interestingly the Floyd algorithm is an itch faster.
Was comparing against the sort/2 algorithm:
cantor_set(X) :- \+ floyd(1, X).
cantor_set2(X) :- sort(X, Y), \+ member(1, Y).
Got these results:
?- time((between(1,100000,_), fuzzy2(X), cantor_set(X), fail; true)).
% 3,185,244 inferences, 0.516 CPU in 0.511 seconds (101% CPU, 6177443 Lips)
true.
?- time((between(1,100000,_), fuzzy2(X), cantor_set2(X), fail; true)).
% 3,095,934 inferences, 0.531 CPU in 0.542 seconds (98% CPU, 5827640 Lips)
true.
The Floyd algorithm can be depicted as:
Edit 29.07.2025:
For the interested programmer, hobby or not hobby.
In Prolog, the 2nd argument is the hare and
the 3rd argument is the tortoise:
floyd(X, Y) :- floyd(X, Y, Y).
floyd(X, [X|_], _).
floyd(X, [_|Y], Z) :- floyd2(X, Y, Z).
floyd2(X, [X|_], _).
floyd2(_, Y, Z) :- same_term(Y, Z), !, fail.
floyd2(X, [_|Y], [_|Z]) :- floyd(X, Y, Z).
I used this fuzzer to generate test data, was using
[D|Y] instead of the Y-D as in the @kuniaki.mukai
test cases that can be found in other threads:
fuzzy2(X) :-
random_between(1,9,M),
fuzzy2_chunk(M,X,Y),
random_between(1,9,L),
fuzzy2_chunk(L,Y,Z),
Z = Y.
fuzzy2_chunk(0, X, X) :- !.
fuzzy2_chunk(N, [D|Y], X) :-
M is N-1,
random_between(0,2,D),
fuzzy2_chunk(M,Y,X).
Your definition of floyd/2 works correctly with negation but it does enumerate each element of the cyclic list twice:
?- L = [1,0,1|L], floyd(1, L).
L = [1, 0, 1|L] ;
L = [1, 0, 1|L] ;
L = [1, 0, 1|L] ;
L = [1, 0, 1|L] ;
false.
I tried to implement a “member for cyclic lists” and I ended up with this:
member_cyc(X, L) :-
L = [_|T],
member_cyc_1(X, L, T).
member_cyc_1(X, Slow, Fast) :-
same_term(Slow, Fast), !,
Slow = [X|_].
member_cyc_1(X, Slow, Fast) :-
( Fast = [_,_|Fast0]
-> [X0|Slow0] = Slow,
( X = X0
; member_cyc_1(X, Slow0, Fast0)
)
; ( Fast = [_] ; Fast = [] )
-> member(X, Slow)
).
Does that look correct to you? This is what it does (comparison to floyd/2):
?- _Flat = [1,0,1], floyd(X, _Flat).
X = 1 ;
X = 0 ;
X = 1 ;
false.
?- _Flat = [1,0,1], member_cyc(X, _Flat).
X = 1 ;
X = 0 ;
X = 1.
?- _Cyclic = [1,0,1|_Cyclic], floyd(X, _Cyclic).
X = 1 ;
X = 0 ;
X = 1 ;
X = 1 ;
X = 0 ;
X = 1 ;
false.
?- _Cyclic = [1,0,1|_Cyclic], member_cyc(X, _Cyclic).
X = 1 ;
X = 0 ;
X = 1.
With the following definition of cantor_set/2 and cantor_set/2:
cantor_set(X) :- \+ member_cyc(1, X).
cantor_set2(X) :- sort(X, Y), \+ member(1, Y).
… and using your fuzzier, I get:
?- time((between(1,100000,_), fuzzy(X), cantor_set(X), fail; true)).
% 3,357,261 inferences, 0.198 CPU in 0.199 seconds (100% CPU, 16913324 Lips)
true.
?- time((between(1,100000,_), fuzzy(X), cantor_set2(X), fail; true)).
% 3,099,035 inferences, 0.205 CPU in 0.205 seconds (100% CPU, 15105160 Lips)
true.
Now the sort is marginally slower, on my computer. Can’t tell if it is correct though 
Note that this is now competing against an algorithm that mutates the list in C. A cycle detection using Floyd’s algorithm wouldn’t mutate the list and must be much faster if implemented in C.
Or maybe 3 times or 4 times etc.. The algorithm is named
after Robert W. Floyd, who was credited with its invention
by Donald Knuth.
The Floyd Algorithm finds a particular start μ of a cycle
and the length λ of a cycle, which are not necessarely
minimal. By the tortoise and hare algorithm, something like:
μ = k , λ = k - 1 or λ = k.
is found. So if you have μ_0 and λ_0 the minimal parameters,
they then get blown up which explains the duplicates.
Any start position shift is also a solution:
μ = μ_0 + s, λ = λ_0
And any period length multiplication is also a solution:
μ = μ_0 + s, λ = λ_0*m
So you can use CLP(FD) to find k, example μ_0 = 13 and λ_0 = 11:
?- [K,S,M] ins 0..1000, K #=13+S,
K #= 11*M #\/ K-1 #= 11*M, label([K,S,M]).
K = 22,
S = 9,
M = 2 .
Most of the time the duplicates are result from shift, the
above example would also have duplicates from multiplication.
The shift and multiplication explains why compare_with_stack/3
goes wrong. Thats the “ambiguity”:
Yes, and I already found a bug in my implementation:
?- _C = [1,2,3|_C], _L = [1|_C], floyd(X, _L).
X = 1 ;
X = 1 ;
X = 2 ;
X = 3 ;
X = 1 ;
X = 2 ;
false.
?- _C = [1,2,3|_C], _L = [1|_C], member_cyc(X, _L).
X = 1 ;
X = 1 ;
X = 2.
I am calling floyd → floyd2 and floyd2 → floyd.
I am only doing same_term/2 in floyd2. So an
additional constraint is that it always finds k > 0,
in case floyd stops searching and fails due to a cycle:
μ = k , λ = k - 1 or λ = k for k > 0.
The tortoise position is k. The hare position is k+k-1
and k+k. The tortoise position is directly the
cycle start μ, the cycle length λ is the distance
between the tortoise and the hare. SWI-Prolog
uses a variation of Floyd’s algorithm called
Brent’s algorithm in pl-prims.c:
Cycle detection for lists using Brent’s algorithm.
skip_list() was originally added to SWI-Prolog by
Ulrich Neumerkel. The code below is a clean-room
re-implementation by Keri Harris.
http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm
I am not sure how sort/2 works. Possibly they first
determine some μ and λ, and from that μ_0 and λ_0, and
sort that. Or maybe they go with the μ and λ ?
You find skip_list() all over the place in SWI-Prolog.
I think my floyd could give a memberchk/2, that directly
works with cyclic lists. But not sure whether it has
really that serious application. More also a vehicle to
think about the problem why a naive compare_with_stack/3
has that many counter examples.