Reputation: 33
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!
Upvotes: 1
Views: 175
Reputation: 18663
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.
Upvotes: 2