Prolog: Swap first and last elements in list

问题:

I'm trying to write a program that swaps the 1st and last elements.

The function takes 2 parameters. A list and a variable that's displayed as the newly swapped list.

I thought I was doing it the lazy way, but it's turning out to be just as hard for me.

I was going to grab the head, put it aside -- grab the last element of the tail, put it aside -- take the tail, remove the last element, put it aside also, then append all 3 together to make a list

I'm having trouble removing the last element of the tail.

I have something like this:

swap( [H|T],  Y ) :-

  % GET HEAD, LAST OF TAIL, AND TAIL WITH LAST ELEM REMOVED

  % GET HEAD (NEW LAST ELEMENT)

   H = NEW_LASTELEMENT,

  % GET LAST ELEMENT (LAST OF TAIL, WILL BE NEW HEAD)

   last(T,X), X = NEWHEAD, 

  % CUT END OF TAIL OFF

   cutlast(T, Z), REST OF CODE . . .

  .



% CUT LAST
cutlast([H | T], [H | T2]) :- T = [_|_], cutlast(T, T2).

I borrowed the cutlast predicate from the web, but I'm not sure how it's even supposed to work. I've been test passing parameters to it for an hour now and they all keep returning false. Any assistance is appreciated.

回答1:

Could be just:

swap(A, B) :-
    append([First | Mid], [Last], A),
    append([Last | Mid], [First], B).

Additional facts to succeed with one element and empty lists, if it's needed:

swap([X], [X]).
swap([], []).

回答2:

Here's a recursive solution that doesn't use the append/3 or reverse/2 built-ins. I think I found it to be a lot more efficient (in terms of number of inferences) than those:

swap_fl_recursive([First|A], [Last|B]) :-
    swap_fl_recursive_(A, First, Last, B).

swap_fl_recursive_([Last], First, Last, [First]).
swap_fl_recursive_([X|A], First, Last, [X|B]) :-
    swap_fl_recursive_(A, First, Last, B).

This solution passes the original First element down through the recursion until it can become the new last element, and instantiates the original Last back to become the new first element.

Like the others, for swap_fl_recursive([X], [X]) to be true or swap_fl_recursive([], []). to be true, those need to be added as facts/rules.

Timing/inferences for append/3 version:

?- numlist(1,10000,L), time(swap_fl_append(L, S)).
% 20,000 inferences, 0.021 CPU in 0.021 seconds (100% CPU, 950838 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
S = [10000, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 3 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 38921 Lips)
false.

Timing/inferences for reverse/2 version:

?- numlist(1,10000,L), time(swap_fl_reverse(L, S)).
% 20,055 inferences, 0.024 CPU in 0.024 seconds (100% CPU, 841265 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
S = [10000, 2, 3, 4, 5, 6, 7, 8, 9|...].

Timing/inferences for recursive version (shown in this answer):

?- numlist(1,10000,L), time(swap_fl_recursive(L, S)).
% 10,000 inferences, 0.009 CPU in 0.010 seconds (99% CPU, 1059142 Lips)
L = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
S = [10000, 2, 3, 4, 5, 6, 7, 8, 9|...] ;
% 2 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 821 Lips)
false.

All three of these approaches are linear time proportional to the length of the list.

回答3:

Here's an alternative version using the built-in reverse/2 instead of append/3.

swap_first_last([First|A], [Last|B]) :-
    reverse(A, [Last|RevMid]),
    reverse([First|RevMid], B).

It's perhaps slightly less efficient than the version Sergey showed with append/3. Like the append/3 version, if you want swap_first_last([X], [X]). and/or swap_first_last([], []). to be true, you have to add them as facts/predicates. But they aren't needed for lists of length 2 or greater.

This predicate says, [Last|B] is the same as [First|A] with the first and last elements swapped if [Last|RevMid] is the reverse of list A, and B is the reverse of [First|RevMid].

The first reverse reverses the tail of the first list (A) yielding a list which has its own head and tail, [Last|RevMid]. At this point, Last represents the last element of the first list, and RevMid represents the "middle" list, not including the first and last elements, but in reverse order.

The second reverse then takes the first list's head, First, and uses it as the head for a new list which is [First|RevMid]. If we reverse this list, we'll end up with the "middle" list in the correct order and First slapped on the end (this list is called B) so we've got the original first element as the last element of this list and all the right middle elements. All that's left is to have the first lists last element (Last) prepended as the head, which occurs in the head of the clause as [Last|B].

By way of example, let's take the query, swap_first_last([a,b,c,d,e], S).:

1. Unify [First|A] with [a,b,c,d,e] yielding, First = a and A = [b,c,d,e]
2. Query reverse([b,c,d,e], [Last|RevMid]) which yields, [Last|T] = [e,d,c,b], or, Last = e and RevMid = [d,c,b].
3. Query reverse([a|[d,c,b]], B) which is reverse([a,d,c,b], B) yielding, B = [b,c,d,a]
4. Instantiating [Last|B] as [e|[b,c,d,a]] or [e,b,c,d,a]

回答4:

Using a dcg:

swap_first_last(Xs,Ys) :-
   phrase(([First],seq(Seq),[Last]),  Xs),
   phrase(([Last], seq(Seq),[First]), Ys).

seq([]) --> [].
seq([E|Es]) --> [E], seq(Es).

But this - similarly to the other suggestions, does not terminate if only Ys is a list. A first attempt would be to constrain the lists to the same length:

same_length([], []).
same_length([_|Xs], [_|Ys]) :-
   same_length(Xs, Ys).

swap_first_last(Xs,Ys) :-
   same_length(Xs, Ys),
   phrase(([First],seq(Seq),[Last]),  Xs),
   phrase(([Last], seq(Seq),[First]), Ys).

But what, if the lists differ in the second element? Like in

?- Xs = [_,a|_], Ys = [_,b|_], swap_first_last(Xs, Ys).
Xs = [b, a],
Ys = [a, b] ;
**LOOPS**

Our predicate still could terminate with:

 swap_first_last(Xs, [Last|Ys]) :-
    phrase(([First],dseq(Ys,[First]),[Last]), Xs).

 dseq(Xs,Xs) --> [].
 dseq([X|Xs0],Xs) --> [X], dseq(Xs0,Xs).