Even and odd cases for the pivot/2 predicate aren't running properly when placed together

Question

My goal is to implement the pivot(Before,After) predicate that returns true when Before's first half is equal to After's second half and Before's second half is equal to After's first half.

With an even number of elements in input list, the lengths of the two halves are same.
With an odd number of elements, the lengths of the two halves are same with the center element doesn't change.

I tried to implement the predicate and it is working but not perfectly. Below is my predicate.

pivot(Before,After) :-
    append(A,B,Before),
    length(A,N),
    length(B,N),
    append(B,A,After).
pivot(Before,After) :-
    append(A,B,Before),
    length(A,N),
    N1 is N + 1,
    length(B,N1),
    append(C,Tail,B),
    length(C,1),
    append(Tail,C,F),
    append(F,A,After).

The pivot(A,[1,2,3,4,5]) is running, but I do not get output.
I am expecting A = [4,5,3,1,2].

Similar code to split a list in half, which you could adapt: https://stackoverflow.com/a/74130437/ — brebs, Dec 09 '22 at 08:47
Use head-and-tail list processing, for efficiency and elegance in Prolog, rather than over-using `append`. — brebs, Dec 09 '22 at 11:18

score 2 · Answer 1 · answered Dec 09 '22 at 09:11

(Assuming you meant pivot not Pivot).

First of all, it is necessary to understand why your current program loops. To understand this, I used a failure-slice. I thus inserted some goals false at a fitting position:

pivot(Before, After) :-
    append(A,B,Before), false,
    length(A, N),
    length(B, N),
    append(B,A,After).
pivot(Before,After) :-
    append(A,B,Before), false,
    length(A, N),
    N1 is N + 1,
    length(B, N1),
    append(C,Tail,B),
    length(C,1),
    append(Tail,C,F),
    append(F,A,After).

?- pivot(A, [1,2,3,4,5]), false.
   loops.

No need to read any further! In the goal append(A,B,Before) the variables A and B occur for the first time, so they cannot influence termination. Only Before may influence it. But in your query that very argument is a variable. If this fragment does not terminate, then the original program does not terminate. And thus in this case, you will always face non-termination. You need to modify this first goal somehow. This example seems to be a good candidate for using a dcg.

slago · Accepted Answer · 2022-12-09T21:01:01.007

A possible solution is:

pivot(In, Out) :-
    pivot(In, In, Left, Middle, Right),
    prepend(Middle, Left, New),
    append(Right, New, Out).

pivot([], Ys, [], [], Ys).
pivot([_], [Y|Ys], [], [Y], Ys).
pivot([_,_|Xs], [Y|Ys], [Y|Left], Middle, Right) :-
    pivot(Xs, Ys, Left, Middle, Right).

prepend([], Xs, Xs).
prepend([X], Xs, [X|Xs]).

How does the predicate work?

?- trace(pivot,+all), pivot([1,2,3,4], L), trace(pivot,-all).
%         pivot/2: [all]
%         pivot/5: [all]
 T [11] Call: pivot([1, 2, 3, 4], _15324)
 T [20] Call: pivot([1, 2, 3, 4], [1, 2, 3, 4], _19198, _19200, _19202)
 T [29] Call: pivot([3, 4], [2, 3, 4], _20104, _19200, _19202)
 T [38] Call: pivot([], [3, 4], _21006, _19200, _19202)
 T [38] Exit: pivot([], [3, 4], [], [], [3, 4])
 T [29] Exit: pivot([3, 4], [2, 3, 4], [2], [], [3, 4])
 T [20] Exit: pivot([1, 2, 3, 4], [1, 2, 3, 4], [1, 2], [], [3, 4])
 T [11] Exit: pivot([1, 2, 3, 4], [3, 4, 1, 2])
%         pivot/2: Not tracing
%         pivot/5: Not tracing
L = [3, 4, 1, 2].

?- trace(pivot,+all), pivot([1,2,3,4,5], L), trace(pivot,-all).
%         pivot/2: [all]
%         pivot/5: [all]
 T [11] Call: pivot([1, 2, 3, 4, 5], _27180)
 T [20] Call: pivot([1, 2, 3, 4, 5], [1, 2, 3, 4, 5], _222, _224, _226)
 T [29] Call: pivot([3, 4, 5], [2, 3, 4, 5], _778, _224, _226)
 T [38] Call: pivot([5], [3, 4, 5], _1680, _224, _226)
 T [38] Exit: pivot([5], [3, 4, 5], [], [3], [4, 5])
 T [29] Exit: pivot([3, 4, 5], [2, 3, 4, 5], [2], [3], [4, 5])
 T [20] Exit: pivot([1, 2, 3, 4, 5], [1, 2, 3, 4, 5], [1, 2], [3], [4, 5])
 T [11] Exit: pivot([1, 2, 3, 4, 5], [4, 5, 3, 1, 2])
%         pivot/2: Not tracing
%         pivot/5: Not tracing
L = [4, 5, 3, 1, 2].

Another examples:

?- length(In, _), pivot(In, Out).
In = Out, Out = [] ;
In = Out, Out = [_] ;
In = [_A, _B],
Out = [_B, _A] ;
In = [_A, _B, _C],
Out = [_C, _B, _A] ;
In = [_A, _B, _C, _D],
Out = [_C, _D, _A, _B] ;
In = [_A, _B, _C, _D, _E],
Out = [_D, _E, _C, _A, _B] ;
In = [_A, _B, _C, _D, _E, _F],
Out = [_D, _E, _F, _A, _B, _C] ;
In = [_A, _B, _C, _D, _E, _F, _G],
Out = [_E, _F, _G, _D, _A, _B, _C]

A comparison of the various suggested solutions for this problem, using SWI-Prolog 8.4.3.

slago(In, Out) :-
    pivot(In, In, Left, Middle, Right),
    prepend(Middle, Left, New),
    append(Right, New, Out).

pivot([], Ys, [], [], Ys).
pivot([_], [Y|Ys], [], [Y], Ys).
pivot([_,_|Xs], [Y|Ys], [Y|Left], Middle, Right) :-
    pivot(Xs, Ys, Left, Middle, Right).

prepend([], Xs, Xs).
prepend([X], Xs, [X|Xs]).


brebs([A,B|T], LstPivot) :-
    same_length([A,B|T], LstPivot),
    pivot_list_half_([A,B|T], [A,B|T], Half1, Half2),
    append(Half2, Half1, LstPivot).

pivot_list_half_([], H2, [], H2).
pivot_list_half_([_|T], [H|Sgl], H1, H2) :-
    pivot_list_half_dbl_(T, H, Sgl, H1, H2).

pivot_list_half_dbl_([], H, H2, [], H2Full) :-
    append(H2, [H], H2Full).
pivot_list_half_dbl_([_|T], H, Sgl, [H|H1], H2) :-
    pivot_list_half_(T, Sgl, H1, H2).


gusbro(Before, After):-
 pivot_df(Before, Before, Before, LAcc-LAcc, LAcc2-LAcc2, After, After, After, RAcc-RAcc, RAcc2-RAcc2).

pivot_df([], _, Before, Before-RightFirstHalf, LeftFirstHalf-[], [], _, After, After-LeftFirstHalf, RightFirstHalf-[]).
pivot_df([_], _, Before, Before-[Middle|RightFirstHalf], LeftFirstHalf-[], [_], _, After, After-[Middle|LeftFirstHalf], RightFirstHalf-[]).
pivot_df([_,_|L1], [A|L2], Before, LAcc-LTail, LAcc2-LTail2, [_,_|L3], [B|L4], After, RAcc-RTail, RAcc2-RTail2):-
  LTail=[A|LTail1], RTail=[B|RTail1],
  LTail2=[A|LTail21], RTail2=[B|RTail21],
  pivot_df(L1, L2, Before, LAcc-LTail1, LAcc2-LTail21, L3, L4, After, RAcc-RTail1, RAcc2-RTail21).


damiano(L,LP):-
    length(L,N),
    N2 is div(N,2),
    findall(E, (nth1(I, L, E), I >= 1, I =< N2), S1),
    (   0 is N mod 2 ->
            findall(E, (nth1(I, L, E), I > N2, I =< N), S2),
            append(S2,S1,LP) ;
            N21 is N2 + 2,
            findall(E, (nth1(I, L, E), I >= N21, I =< N), S2),
            N11 is N2 + 1,
            nth1(N11,L,El),
            append([El],S1,S11),
            append(S2,S11,LP)
    ).


comparison :-
    format('  Length  Slago    Brebs    Gusbro   Damiano\n', []),
    forall(between(1, 8, I),
           (   N is 10^6*I,
               length(L, N),
               findall(T,
                       ( member(P, [slago, brebs, gusbro, damiano]),
                         runtime(P, L, T)),
                       Ts),
               format('~|~t~w~8+ ~|~t~5f~8+ ~|~t~5f~8+ ~|~t~5f~8+ ~|~t~5f~8+\n', [N|Ts]) )).


runtime(P, L, T) :-
    garbage_collect,
    T0 is cputime,
    call(P, L, _),
    T is cputime - T0.

Results:

?- comparison.
  Length  Slago    Brebs    Gusbro   Damiano
 1000000  0.04688  0.07812  0.68750  0.60938
 2000000  0.09375  0.17188  0.92188  1.23438
 3000000  0.15625  0.26562  0.67188  1.92188
 4000000  0.21875  0.35938  1.84375  2.60938
 5000000  0.28125  0.46875  1.10938  3.35938
 6000000  0.32812  0.56250  1.35938  3.87500
 7000000  0.39062  0.64062  3.21875  4.67188
 8000000  0.45312  0.70312  3.51562  5.20312
true.

Gusbro's solution caused stack overflow for list with length 9000000.

I've improved mine, to avoid `same_length` in the usual usage, for performance. Mine and yours are almost identical, with mine having improvements for determinism with `([a, b, c], P)`, and for not going to infinity with `(L, [a, b])` :-) — brebs, Dec 10 '22 at 11:15
@brebs Nice! In fact, these improvements can easily be done in my version as well. But even after the modifications, my version is still up to 20% faster than yours. I think this is due to the call to `append/3`, which you make in the base case of your predicate `pivot_list_half_dbl_/5`. — slago, Dec 10 '22 at 13:37
@slago: Your solution seems to get in loop for queries like this: `pivot(A,[a]).` when backtracking for further solutions — gusbro, Dec 12 '22 at 21:47
@gusbro Yes, I know it! As I said in a previous comment, that can be easily solved by calling the predicate `same_length/2` in `pivot/2`. — slago, Dec 12 '22 at 22:58

score 0 · Answer 3 · answered Dec 09 '22 at 11:11

Here is a possibly cumbersome solution (using SWI prolog), inspired by this question/answer

pivot(L,LP):-
    length(L,N),
    N2 is div(N,2),
    findall(E, (nth1(I, L, E), I >= 1, I =< N2), S1),
    (   0 is N mod 2 ->
            findall(E, (nth1(I, L, E), I > N2, I =< N), S2),
            append(S2,S1,LP) ;
            N21 is N2 + 2,
            findall(E, (nth1(I, L, E), I >= N21, I =< N), S2),
            N11 is N2 + 1,
            nth1(N11,L,El),
            append([El],S1,S11),
            append(S2,S11,LP)
    ).
        
?- pivot([1,2,3,4,5],L).
L = [4, 5, 3, 1, 2]
?- pivot([1,2,3,4],L).
L = [3, 4, 1, 2]
?- pivot([],L).
L = []

score 0 · Answer 4 · answered Dec 09 '22 at 16:39

Here goes a solution using difference lists which does not require to use append and the like:

pivot(Before, After):-
 pivot(Before, Before, Before, LAcc-LAcc, LAcc2-LAcc2, After, After, After, RAcc-RAcc, RAcc2-RAcc2).

pivot([], _, Before, Before-RightFirstHalf, LeftFirstHalf-[], [], _, After, After-LeftFirstHalf, RightFirstHalf-[]).
pivot([_], _, Before, Before-[Middle|RightFirstHalf], LeftFirstHalf-[], [_], _, After, After-[Middle|LeftFirstHalf], RightFirstHalf-[]).
pivot([_,_|L1], [A|L2], Before, LAcc-LTail, LAcc2-LTail2, [_,_|L3], [B|L4], After, RAcc-RTail, RAcc2-RTail2):-
  LTail=[A|LTail1], RTail=[B|RTail1],
  LTail2=[A|LTail21], RTail2=[B|RTail21],
  pivot(L1, L2, Before, LAcc-LTail1, LAcc2-LTail21, L3, L4, After, RAcc-RTail1, RAcc2-RTail21).

Sample runs:

?- pivot([1,2,3,4,5], After).
After = [4, 5, 3, 1, 2] ;
false.

?- pivot([1,2,3,4], After).
After = [3, 4, 1, 2] ;
false.

General query:

?- pivot(Before, After).
Before = After, After = [] ;
Before = After, After = [_] ;
Before = [_A, _B],
After = [_B, _A] ;
Before = [_A, _B, _C],
After = [_C, _B, _A] ;
Before = [_A, _B, _C, _D],
After = [_C, _D, _A, _B] ;
Before = [_A, _B, _C, _D, _E],
After = [_D, _E, _C, _A, _B] ;
Before = [_A, _B, _C, _D, _E, _F],
After = [_D, _E, _F, _A, _B, _C] ;
Before = [_A, _B, _C, _D, _E, _F, _G],
After = [_E, _F, _G, _D, _A, _B, _C] .

brebs · Answer 5 · 2022-12-10T18:04:08.693

Similar to https://stackoverflow.com/a/74130437/

Edited to use same_length only when necessary, to improve performance.

Edited again to use list_to_dl instead of append, for a tiny performance improvement.

pivot_list_half([A,B|T], LstPivot) :-
    (   is_list([A,B|T]) -> true
        % Preventing infinity with: pivot_list_half(L, [a, b])
        % whilst keeping performance for usual usage
    ;   same_length([A,B|T], LstPivot)
    ),
    pivot_list_half_([A,B|T], [A,B|T], Half1, Middle, Half2),
    list_to_dl(Half2, LstPivot, Half2Tail),
    list_to_dl(Middle, MiddleDL, MiddleTail),
    % Join the tails
    (Half2Tail, MiddleTail) = (MiddleDL, Half1).

pivot_list_half_([], H2, [], [], H2).
pivot_list_half_([_|T], [H|Sgl], H1, Mid, H2) :-
    pivot_list_half_dbl_(T, H, Sgl, H1, Mid, H2).
    
pivot_list_half_dbl_([], H, H2, [], [H], H2).
pivot_list_half_dbl_([_|T], H, Sgl, [H|H1], Mid, H2) :-
    pivot_list_half_(T, Sgl, H1, Mid, H2).

list_to_dl([], T, T).
list_to_dl([H|T], [H|T2], Tail) :-
    list_to_dl(T, T2, Tail).

Results in swi-prolog:

% Deterministic, with both arguments
?- pivot_list_half([a, b, c, d, e], P).
P = [d, e, c, a, b].

?- pivot_list_half(L, [a, b]).
L = [b, a].

?- pivot_list_half(L, P).
L = [_A, _B],
P = [_B, _A] ;
L = [_A, _B, _C],
P = [_C, _B, _A] ;
L = [_A, _B, _C, _D],
P = [_C, _D, _A, _B] ;
L = [_A, _B, _C, _D, _E],
P = [_D, _E, _C, _A, _B] ;
L = [_A, _B, _C, _D, _E, _F],
P = [_D, _E, _F, _A, _B, _C] ;

score -1 · Answer 6 · answered Dec 09 '22 at 22:41

Here's a solution using difference lists. We walk the source list at two different speeds:

2 elements at a time. This tells us when we've found the middle of the list:
- if the list is reduced to the empty list ([]), the list is of even length and there is no middle element: we just reconstruct the list with the left and right halves swapped.
- if the list is reduced to a list of length 1, we've found the middle element: we reconstruct the list with the left and right halves swapped about the middle element.
1 element at a time. This provides the elements to construct the left half of the list as we go, and ultimately provides the middle element (if their is one), and the right half.

https://swish.swi-prolog.org/p/WjOUnQjJ.pl

pivot( Bs , As ) :- var(Bs), var(As), !, fail .
pivot( Bs , As ) :- var(Bs),          !, pivot(As,Bs) .
pivot( Bs , As ) :-                      pivot(Bs,Bs,L-L,As) . 

pivot( []       ,    Rs  , Ls-[]     , Ps ) :- append(Rs,Ls,Ps) .      % even length list
pivot( [_]      , [M|Rs] , Ls-[]     , Ps ) :- append(Rs,[M|Ls],Ps) .  % odd length list
pivot( [_,_|Xs] , [L|Rs] , Ls-[L|Lx] , Ps ) :- pivot(Xs,Rs,Ls-Lx,Ps) . % take 2 and take 1 and recurse down, building the left half as we go

Even and odd cases for the pivot/2 predicate aren't running properly when placed together

6 Answers6