1

The problem of how to generate subsets is well answered by this question. My question is about why my code does not. My own attempt at the problem was

subset2(_, []).
subset2(Set, [S|Subset]) :- member(S, Set), not(member(S, Subset)), subset2(Set, Subset).

While this does correctly test for subsets, it will only generate the emptyset. Why is this?

Mark
  • 672
  • 1
  • 6
  • 19

1 Answers1

1

The line not(member(S, Subset)) happens before Subset has any known value. In that case it's saying "one thing we know about Subset is that it's a list with S in it!". You're telling Prolog to put S into Subset, then asking if doing that failed.

e.g. it will fill in unknown variables in lists:

?- member(horse, [cat, dog, sheep, PLACEHOLDER, cow, pig]).
PLACEHOLDER = horse

asks:

  • does horse unify with cat? no.
  • does horse unify with dog? no.
  • does horse unify with sheep? no.
  • does horse unify with PLACEHOLDER? Yes! uninitialised variables can unify with atoms, solved!

or it can generate longer and longer lists with the thing in it at each position:

?- member(horse, ANIMALS).
ANIMALS = [horse|_1690] ;
ANIMALS = [_1408, horse|_1416] ;
ANIMALS = [_1408, _1414, horse|_1422] ;
ANIMALS = [_1408, _1414, _1420, horse|_1428] ;
TessellatingHeckler
  • 27,511
  • 4
  • 48
  • 87
  • Is this a general warning against using negation as failure to generate variable instantiations? Does it never work? – Mark May 20 '22 at 17:54
  • 1
    @Mark I don't have enough experience to say 'never' for sure, but I think that's right. In your code you are trying to say what Subset *isn't* but not really ever saying what it *is* or how to build it. For that you need code like "generate some possibles, not that one". – TessellatingHeckler May 20 '22 at 23:00