Lists are not sets, Prolog is not logic

In Ivan Bratko's Prolog. Programming for Artificial Intelligence, in the part introducing lists, there's an obvious exercise consisting in writing a program that gives all the subsets of a given list. In terms of Prolog: a predicate subset(Set,Subset), where all the elements of Subset are elements of Set.

The task seems elementary, but in fact it's quite tricky. The program I wrote did only half of the job, and when (after a half an hour of frantic debugging) I eventually checked the author's program in the Solutions, it turned out that it neither did all the job properly. The interesting point is that this example shows how logic background may in some cases influence your programming intuitions.

But first things first--the two programs and what is wrong with them. The “canonical” solution is the following:

subset([],[]).

subset([First|Rest],[First|Sub]) :-
  subset(Rest,Sub).

subset([First|Rest],Sub) :-
  subset(Rest,Sub).

My solution is a bit simpler:

m_subset(Set,[]).

m_subset(X,[Y|Tail]) :-
  m_subset(X,Tail),
  member(Y,X).

What's wrong with the two programs? Well, the canonical version deals fine with generating all the subsets of a given set/list--that is, when you give Prolog the following command:

subset([1,2,3],X).

However, when it turns to checking whether there is inclusion between two given sets, it appears to be quite lame: it won't give you the correct answer unless the two lists are given in the same order. That is, it says “no” to the query

subset([1,2,3],[3,2]).

(I have to make a remark that the stipulation that the lists should be sorted in the same way wasn't given in the text of the exercise).

My program, on the other hand, is great in determining if there is an inclusion, but as for the second task... Well, it just doesn't stop in the right moment. That is, after generating all the subsets of [1,2,3] it starts saying

[1,2,3,1] ;
[1,2,3,2] ;
[1,2,3,3] ;
...

etc.

In fact, that is true (if we want to use lists to represent sets, we should ignore any double occurrences), but if I wanted to have a list of all subsets and manipulate it, an infinite list would not really be the best thing.

I claim that my definition of subset is good, and in some aspects even superior over Bratko's: it is shorter, it's more intuitive, it takes account of some trivial set-theoretic facts the latter ones ignore (like for example that the empty set is a subset of every set). The only problem is that lists just aren't sets (very surprising, isn't it?), and they have different conditions of identity. So when Prolog finds the four element list, which represents a set that already was given, it thinks it is something new. Well, and (sadly), Prolog it's completely right: it is something new.

Now, this problem allows us to observe the fact that Prolog, even if it is not an imperative but a declarative programming language, it is still a programming language, not logic. And things like infinite classes just aren't good. So, my approach towards it should be more as my approach towards e.g. scheme than to logic. And that's why, even if my program was directly translatable to predicate calculus and set theory (of course, limited to Horn clauses), it just wouldn't do.