Search code examples
prolog

Prolog subsets generation

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?

Solution

  • 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] ;