Re: Complex Subset Computing in Prolog

On Mon, 29 Dec 2008 00:46:23 -0800, bird5467 wrote:

On 28 Dez., 17:47, prolognerd <hm.ja...@xxxxxxxxx> wrote:
Hi,
your subset rule does not deliver the correct subsets. Cu
Josef- Hide quoted text -

- Show quoted text -

Josef,

I think they do, specially for ground terms. For example for terms such
as subset([1,4],[4,2,3,1,6]), it works just fine. I needed this rule
because I did not want it to be order dependent. But the problem is
with goals like subset([X,Y],[4,2,3,1,6]), it does not work properly.
It may so happen that unification will make X=4 and Y=4 and succeed,
because they are tried as member(X,[4,2,3,1,6]), fof example and then
again member(Y,[4,2,3,1,6]). In both case it succeeds with X=4 and Y=4.

But if you try to unify p([X,Y]) with p([4,1]), it will prefectly
produce X=4, and Y=1, and fail for p(4,1,3]).


Yes. But in your example you complain that you get two 'a'. And thats
exactly because the arguments to subset are not ground and the subset
contains multiple elements.

I see the problem, that the sets/lists are not ordered. Solutions could
be:
a) Sort the input sets/lists and work with the sorted lists b) Use a
real subset and permutate them to handle all orders c) Claim explicit W
=/= X, X =/= Y,... or if the number of
variables is unknown build something like distinct(List).

I don't know your original problem. E.g. it is not clear for me whether
in the e([X,Y]) term are always two elements or more.

Cu
Josef

There is often confusion when lists and sets are used (in Prolog or
any other language, but let's do this for Prolog) and this pops up
almost always when the subset predicate raises its head.

Here is the origin of this confusion in a nutshell:

- a set is a mathematical concept (just like a tree or an algebra)
- a list is a Prolog data structure

One can use Prolog lists to represent a set, for instance the set

{x,a,p}

can be represented by the Prolog list [x,a,p], and here comes the
problem: you can also represent it as [a,p,x] (and some 4 more
permutations of that list). You are even free to represent the same
set as the Prolog list [a,x,x,p,a], which contains duplicates, even
though sets don't. Meaning that you can choose to have a set as Prolog
list representation that is not unique. That is perfectly ok, and it
gets you into trouble in many situations. It is usually better to have
a unique representation of every set. But let's not go into which is
"better" because it depends on what you are doing. The important
thing is however:

you must know what you are doing, and it helps to make it explicit



So, if you meant

a set S is represented by any list that contains all the members of S
at least once in any order and no other elements

then the predicate

subset([X|R],S) :- member(X,S), subset(R,S).
subset([],_).

says

the first argument represents a subset of the set represented in
the second argument

and you are doing fine. And don't be surprised that the number of
solutions to your subset/2 is infinite, even if the second argument is
ground.


However, if you want your representation to have certain properties of
sets (e.g. unique elements), then you better make sure that your
predicates cater for that, because you are not getting it for free !
A sorted list without duplicates would then be a good representation.
And the number of solutions to a subset/2 predicate (when the second
argument is ground) will be 2^N as in mathematics.


Cheers

Bart Demoen
.

Relevant Pages

  • Re: Complex Subset Computing in Prolog
    ...    variables is unknown build something like distinct. ... There is often confusion when lists and sets are used (in Prolog or ... but let's do this for Prolog) and this pops up ... list representation that is not unique. ...
    (comp.lang.prolog)
  • Re: Complex Subset Computing in Prolog
    ...    variables is unknown build something like distinct. ... There is often confusion when lists and sets are used (in Prolog or ... but let's do this for Prolog) and this pops up ... list representation that is not unique. ...
    (comp.lang.prolog)
  • Re: Hilbert-Style proof in propositional calculus
    ... The topic lends itself to Prolog. ... about the representation of formulas as Prolog terms and ... We can then implement a Prolog predicate which succeeds ... Now let's briefly discuss representing proofs as lists ...
    (comp.lang.prolog)
  • Re: An instance of Russells paradox?
    ... >>> of lists is actually syntactic sugar for the binary term ... >>> such as philosopherand the prefix list representation of it. ... >>alternative Prolog notations for the same term: ... >>notation, the list notation, and the operator notation. ...
    (sci.logic)
  • Re: Modeling Address using Relational Theory
    ... >> address (not a representation of one). ... lists are typically modeled as lists ... One operation on the data is an operation to order addr2 after ... be able to adjust much more handily than if I put addr2 before addr1 on ...
    (comp.databases.theory)
Loading