create circled List in Prolog

Question

I'm trying to create this function in Prolog:

% Signature: circleList(L1, L2)/2
% Purpose: L2 is a "circled" L1 list.
% Precondition: L1 is fully instantiated.
% Examples:
% ?- circleList([2, 3, 4, 5], X).
% X = [2, 3, 4, 5];
% X = [3, 4, 5, 2];
% X = [4, 5, 2, 3];
% X = [5, 2, 3, 4];
% false.

so i did this:

circleList([],[]).
circleList(X,X).
circleList([H|T],R):- append(T,[H],S), circleList(S,R).

but the output is this:

X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] 
and so on...

this is good but i want to make it stop after the first time i'm doing the whole possibilities.

what can i do?

Tudor Berariu · Answer 1 · 2014-06-10T14:14:25.020

You need another argument to your predicate. One option is to consume the elements in your list until you are left with [].

circleList([Head|Tail],CL):-
    circleList(Tail,[Head],CL).

circleList([],L,L).
circleList([Head|Tail], Rest, CL):-
    append(Rest, [Head], NewRest),
    circleList(Tail, NewRest, CL).
circleList([Head|Tail], Rest, CL):-
    append([Head|Tail], Rest,CL).

Another option I see is limiting the depth to the size of the list using length/2.

circleList([],[]).
circleList(List,CL):-
    length(List, N),
    circleList(List,N,CL).

circleList(_,0,_):-!, fail.
circleList(List,_,List).
circleList([Head|Tail], N, CL):-
    append(Tail, [Head], NewList),
    N1 is N - 1,
    circleList(NewList, N1, CL).

false · Answer 2 · 2014-06-10T14:17:22.403

3

You might simply formulate the problem differently:

rotatelist([], []).
rotatelist(Xs, Ys) :-
   Xs = [_|_],
   Ys = [_|_],
   same_length(Xs, Ys), % avoid non-termination
   Bs = [_|_],          % avoid redundant answers
   append(As,Bs,Xs),
   append(Bs,As,Ys).

same_length([], []).
same_length([_E|Es], [_F|Fs]) :-
   same_length(Es, Fs).

But if your point is to explicitly stop ; well, that can easily turn out to be incorrect. In fact, I do not see a natural way how a cut might be used here.

You might, however, limit the number of recursions like so:

circleList2(Xs, Ys) :-
   same_length(Xs, Ys),
   circleList2(Xs, Ys, Xs).

circleList2(X,X, _).
circleList2([H|T],R, [_|L]):-
   L = [_|_],
   append(T,[H],S),
   circleList2(S,R, L).

So this is essentially your program with one additional argument used to limit the number of recursions. Limiting recursion in such a manner is commonly used to implement so called iterative deepening algorithms. In this case, however, we had a single depth bound. No extra iteration was necessary.

edited Jun 10 '14 at 14:17

answered Jun 10 '14 at 14:08

false

10,264
13
101
209

I can't limit it and i can't create a predicate with 3 variables unless it's like a "helping function". this is from an assignment i have about the basics of Relational Logic programming using Prolog, so i need a better explanation please – kitsuneFox Jun 10 '14 at 14:28
1

@kitsuneFox: Why can't you limit it??? same_length/2 and circleList2/3 are auxiliary predicates. – false Jun 10 '14 at 14:33
1

@TudorBerariu: Because that loops for `circleList(L,[1,2])` and it produces a redundant solution for, say `circleList([1,2],L)`. – false Jun 10 '14 at 14:36
My deleted question for @false was: why a simpler form like `circleList4(L1, L2):-append(A, B, L1), B = [_|_], append(B, A, L2).` wasn't enough in his first solution. – Tudor Berariu Jun 10 '14 at 14:38
@kitsuneFox: So you have now two solutions to chose from: `rotatelist/2` and `circleList/2`. – false Jun 10 '14 at 14:38
@false: No, it doesn't loop and it doesn't produce any redundant solutions, but it doesn't work for `circleList([],L).`. – Tudor Berariu Jun 10 '14 at 14:40
@TudorBerariu, it seems that solution works, and looks a way easier to understand, which is good for a Prolog-beginner like me. one question thou,what is B = [_|_] mean? – kitsuneFox Jun 10 '14 at 14:40
It means that `B` must have at least one element. You unify that list (`B`) using two parts: its head (first element) and its tail. – Tudor Berariu Jun 10 '14 at 14:42
@TudorBerariu: There is an extra fact for `[]`: `rotatelist([],[])`! – false Jun 10 '14 at 14:42
@TudorBerariu, your append looks different from mine and i don't think i'm familier with yours...where does those A and B variables come from? – kitsuneFox Jun 10 '14 at 17:33
1

The goal `append(A, B, L).` with two unbound variables `A`, `B` is satisfied for all lists `A`,`B` that concatenated give the result `L`. (e.g. `?- append(A,B,[a,b,c]). A = [], B = [a, b, c] ; A = [a], B = [b, c] ; A = [a, b], B = [c] ; A = [a, b, c], B = [] ; false.`) – Tudor Berariu Jun 10 '14 at 19:40
This idiom (the inner loop of iterative-deepening search) is commonly called depth-limited search when used on its own. – Fred Foo Jun 11 '14 at 11:23
@larsmans: By stressing this as "search", any Prolog program is a search program. In a sense yes, but I think that this is not the ideal notion to convey. – false Jun 11 '14 at 11:29
Backtracking search is the backbone of Prolog :) – Fred Foo Jun 11 '14 at 12:43
@larsmans: Indeed, but is it a good idea to repeat such imperative notions all the time? Aren't people already full of this command-oriented thinking? – false Jun 11 '14 at 12:45
That's a generalization. Some people ask questions here on SO like "why doesn't Prolog get my logic" when they have an infinite loop, meaning they're thinking too logically. Algorithm = Logic + Control; you always need both. – Fred Foo Jun 11 '14 at 13:23
@larsmans: Please show me one question where someone thought "too logically". And **some** infinite loops are logically necessary. – false Jun 11 '14 at 13:27
1

http://stackoverflow.com/q/8108632/166749, http://stackoverflow.com/q/20060840/166749 – Fred Foo Jun 11 '14 at 14:53
@larsmans: Hmhm. The logic involved in this example is not very involved. Socrates. When thinking "too logically" I had expected something that goes beyond introductory examples. – false Jun 11 '14 at 14:58
@larsmans: Your second example is a logical error: http://stackoverflow.com/a/24166956/772868 – false Jun 11 '14 at 15:34
@TudorBerariu, i'm trying to understand the logic behind your solution, and i find it a bit tough for me...can you show me the steps and all the intermediates on a simple example like circleList([1,2,3],X)? – kitsuneFox Jun 12 '14 at 08:08

false · Answer 3 · 2022-08-19T17:51:31.903

Here is a simpler solution with much weaker termination properties. On the other hand you stated that the first argument is "fully instantiated". Can you, quickly, produce a test for an argument to be "fully instantiated"? I assume not. And it is for this reason that such assumptions lead to so many errors. First, programmers just assume that the argument will be "fully instantiated" and later they forget what they assumed...

circleList3(Xs, Ys) :-
   append(As, Bs, Xs),
   append(Bs, As, Ys),
   ( As = [] ; As = [_|_], Bs = [_|_] ).

This version now does no longer terminate for circleList3(Xs, []). To see why this is so, I will use a failure-slice that is, I will add false in the program. If the remaining part still does not terminate, then one problem lies in the visible part.

?- circleList3(Xs, []), false.
   loops.

circleList3(Xs, Ys) :-
   append(As, Bs, Xs), false,
   append(Bs, As, Ys),
   ( As = [] ; As = [_|_], Bs = [_|_] ).

This failure slice does not terminate, because the first goal is called with 3 uninstantiated arguments. The only help to get this terminating would be Ys, but nobody is interested in it!

We could now exchange the two goals append/3 making this fragment terminate, but then, other queries would not terminate...

create circled List in Prolog

3 Answers3