'Prolog program that swaps the two halves of a list

I am new to this language and am having trouble coming up with a solution to this problem. The program must implement the following cases.

  • Both variables are instantiated:

    pivot( [1,2,3,4,5,6,7], [5,6,7,4,1,2,3] ).`

    yields a true/yes result.

  • Only Before is instantiated:

    pivot( [1,2,3,4,5,6], R ).

    unifies R = [4,5,6,1,2,3] as its one result.

  • Only After is instantiated:

    pivot(L, [1,2]).

    unifies L = [2,1] as its one result.

  • Neither variable is instantiated:

    pivot(L, R).

    is undefined (since results are generated arbitrarily).

prolog


Solution 1:[1]

If by pivot, you mean to split the list in 2 and swap the halves, then something like this would work.

First, consider the normal case: If you have an instantiated list, pivoting it is trivial. You just need to

  • figure out half the length of the list
  • break it up into
    • a prefix, consisting of that many items, and
    • a suffix, consisting of whatever is left over
  • concatenate those two lists in reverse order

Once you have that, everything else is just a matter of deciding which variable is bound and using that as the source list.

It is a common Prolog idiom to have a single "public" predicate that invokes a "private" worker predicate that does the actual work.

Given that the problem statement requires that at least one of the two variable in your pivot/2 must be instantiated, we can define our public predicate along these lines:

pivot( Ls , Rs ) :- nonvar(Ls), !, pivot0(Ls,Rs) .
pivot( Ls , Rs ) :- nonvar(Rs), !, pivot0(Rs,Ls) .

If Ls is bound, we invoke the worker, pivot0/2 with the arguments as-is. But if Ls is unbound, and Rs is bound, we invoke it with the arguments reversed. The cuts (!) are there to prevent the predicate from succeeding twice if invoked with both arguments bound (pivot([a,b,c],[a,b,c]).).

Our private helper, pivot0/2 is simple, because it knows that the 1st argument will always be bound:

pivot0( Ls , Rs ) :-   % to divide a list in half and exchange the halves...
  length(Ls,N0)      , % get the length of the source list
  N is N0 // 2       , % divide it by 2 using integer division
  length(Pfx,N)      , % construct a unbound list of the desired length
  append(Pfx,Sfx,Ls) , % break the source list up into its two halves
  append(Sfx,Pfx,Rs)   % put the two halves back together in the desired order
  .                    % Easy!

Solution 2:[2]

In swi-prolog:

:- use_module(library(dcg/basics)).

pivot_using_dcg3(Lst, LstPivot) :-
    list_first(Lst, LstPivot, L1, L2, IsList),
    phrase(piv3_up(L1), L1, L2),
    % Improve determinism
    (IsList = true -> ! ; true).

piv3_up(L), string(Ri), string(M), string(Le) --> piv3(L, Le, M, Ri).

piv3([], [], [], Ri) --> [], remainder(Ri).
piv3([_], [], [H], Ri) --> [H], remainder(Ri).
piv3([_, _|Lst], [H|T], M, Ri) --> [H], piv3(Lst, T, M, Ri).

% From 2 potential lists, rearrange them in order of usefulness
list_first(V1, V2, L1, L2, IsList) :-
    (   is_list(V1) ->
        L1 = V1, L2 = V2,
        IsList = true
    ;   L1 = V2, L2 = V1,
        (is_list(L1) -> IsList = true ; IsList = false)
    ).

Is general and deterministic, with good performance:

?- time(pivot_using_dcg3(L, P)).
% 18 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 402441 Lips)
L = P, P = [] ;
% 8 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 238251 Lips)
L = P, P = [_] ;
% 10 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 275073 Lips)
L = [_A,_B],
P = [_B,_A] ;
% 10 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 313391 Lips)
L = [_A,_B,_C],
P = [_C,_B,_A] ;
% 12 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 321940 Lips)
L = [_A,_B,_C,_D],
P = [_C,_D,_A,_B] ;
% 12 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 345752 Lips)
L = [_A,_B,_C,_D,_E],
P = [_D,_E,_C,_A,_B] ;
% 14 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 371589 Lips)
L = [_A,_B,_C,_D,_E,_F],
P = [_D,_E,_F,_A,_B,_C] ;

?- numlist(1, 5000000, P), time(pivot_using_dcg3(L, P)).
% 7,500,018 inferences, 1.109 CPU in 1.098 seconds (101% CPU, 6759831 Lips)

The performance could be improved further, using difference lists for the final left-middle-right append, and cuts (sacrificing generality).

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Nicholas Carey
Solution 2

Related Questions