Recursion through a list in Prolog

Question

I'm trying to reverse a list in Prolog. It works OK when I call it with ['item1', 'item2'] but not when calling it with ['item1'|'item2']. I'm at beginner level with Prolog, but I thought that these two notations were essentially interchangeable?

Here's the code I'm using:

reverse_list([], Acc, Acc).
reverse_list([Head|Tail], Acc, Reversed) :-
    reverse_list(Tail, [Head|Acc], Reversed). 

reverse_list(List,Reversed) :-
    reverse_list(List,[],Reversed).

The problem is when making the recursive call with the tail of the list

When I call it with list ['item1', 'item2'], the debugger shows that it works correctly, making a recursive call with the tail as ['item2'], as it should be.

When I call it with ['item1'|'item2'], the debugger shows that it tries to make a recursive call with 'item2', which fails, presumably because it's not a list.

I read that the Tail will always be a list when using [Head|Tail], but it looks like that isn't the case here.

Could you explain how Prolog is handling these lists, and why these two ways of representing lists aren't interchangeable? Could you explain how to make this code work?

Thanks!

[First | Rest]. So, in [1,2,3,4], First = 1 and Rest = [2,3,4,5]. — AJF
While I'm at it, you could define it nicely using foldl. first, cons(X,Xs,[X|Xs])., then reverse(A,B) :- foldl(cons, A, [], B). — AJF

Paulo Moura Paulo Moura · Accepted Answer · 2015-02-21T22:47:21

The tail of a list is a list. For example:

| ?- [1,2,3] = [Head| Tail].
Head = 1
Tail = [2,3]
yes

The compound term you're using as argument, ['item1'|'item2'], is not a list:

| ?- ['item1'|'item2'] = [Head| Tail].
Head = item1
Tail = item2
yes

You need to write instead [item1|[item2]], which is the exact same thing as [item1,item2]:

| ?- [item1|[item2]] = [item1,item2]. 
yes

As list notation is syntactic sugar, you can use the standard write_canonical/1 predicate to examine a list structure:

| ?- write_canonical([1,2,3]).       
'.'(1,'.'(2,'.'(3,[])))
yes

| ?- write_canonical([item1, item2]).
'.'(item1,'.'(item2,[]))
yes

| ?- write_canonical([item1| item2]).
'.'(item1,item2)
yes

When calling reverse_list([item1|[item2]], Reversed), the goal fails at the first recursive call as you get reverse_list(item2, ..., ...), which doesn't unify with any of the heads of the clauses for the reverse_list/3 predicate and thus cannot be proved. Thus, there's nothing wrong with your predicate definitions. Just a misunderstanding on list representation.

Recursion through a list in Prolog

1 Answers