Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
% Credit to Rosetta Code [1], with modifications
% [1]:
% Here, X is the thing we want the powerset of, and Y will contain
% the powerset.
% We are defining the powerset as being a "bag" of all subsequences `S`
% (there is already a Prolog function called `subset`) of the set `X`,
% with the results collected into `Y`.
powerset(X,Y) :- bagof(S, subseq(S,X), Y).
% This says that the empty list is a subsequence of itself, and that the empty
% list is a subsequence of any list with a head and a tail (the `[_|_]` notation),
% together, these make sure the empty list is given as a subsequence of all lists.
% Then is says that a subsequence of a list is defined as containing the first
% element of the list, plus a subsquence of the rest.
% Finally, it says a subsequence is some element in any position of the original
% list, plus a subsequence of the rest of the list.
% Notice that collectively, this doesn't say how to find those subsequences, it
% says what a subsequence _is_. Prolog then searches for subsequences using these
% rules.
% Also note that Prolog would usually stop after finding one subsequence, but that
% `bagof` makes it keep going until all the subsequences have been found.
subseq([], []).
subseq([], [_|_]).
subseq([X|Xs], [X|Ys] ) :- subseq(Xs, Ys).
subseq([X|Xs], [_|Ys] ) :- append(_, [X|Zs], Ys), subseq(Xs, Zs).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment