CODEWITHSUNDEEP
prolog
kvway
kvway

Reputation: 494

Rotate a list in prolog recursively

I'm trying to rotate a list in prolog recursively but it does not work as expected.

Code:

rot([],[]).
rot([H|T1], [T2|H]):-rot(T1,T2).

Output:

?- rot([1,2,3], V).
V = [[[[]|3]|2]|1]

Expected output:

?- rot([1,2,3], V).
V = [3,2,1]

Could anyone explain me why my code does not work?

Upvotes: 2

Views: 302

Answers (3)

bob_saginowski
bob_saginowski

Reputation: 1429

The problem is with the second clause. What I do is to rotate the tail of the first list inside L1 and then call append with L1 and the first element and assign the result to L (the second argument)

my-append([], L, L).
my-append([H|T], L, [H|R]) :- my-append(T, L, R).

rot([], []).
rot([H|T], L) :- rot(T, L1), my-append(L1, H, L).

Upvotes: 2

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476614

Since Prolog is untyped, you can indeed write something like [List|Element], but if you want a list to make sense, the only way you can construct lists is like [Element|List]. So [T2|H] does not make sense at all. In that case T2 should be an element, and H a list (or the empty list []).

You will need to define two predicates:

  • the main predicate (rot/2) that simply pops the head from the given list and calls the recursive predicate; and
  • the recursive predicate (here rot/3) that simply passes all elements of the given list and emits the original head as tail element.

Together this works like:

%main predicate rot/2
rot([],[]).
rot([H|T1],T2) :-
    rot(T1,H,T2).

%recursive predicate rot/3
rot([],Last,[Last]).
rot([H|T1],Last,[H|T2]) :-
    rot(T1,Last,T2).

Upvotes: 4

Daniel Lyons
Daniel Lyons

Reputation: 22803

Your code doesn't work because in an expression like [H|T], H is an element of the list and T is the tail of the list--also a list. For instance:

?- [H|T] = [1,2,3].
H = 1,
T = [2, 3].

So what happens when you switch that around?

?- [H|T] = [1,2,3], X = [T|H].
H = 1,
T = [2, 3],
X = [[2, 3]|1].

See the problem?

Upvotes: 3

Related Questions