Creating a set from a list in Prolog

3
votes

So basically my task is to create a Set out of a given List with a predicate containing 2 parameter.

The first one is the list and the second is the Set´s value.

However somehow it gives me a List which contains the Set as the Head and a Tail with a variable:

2 ?- list2set([2,3,4,4] , X).
X = [2, 3, 4|_G2840] .

thats the code:

list2set( [] , _).
list2set([ListH|ListT] , Set ) :- member(ListH, Set) , list2set(ListT , Set).

It seems to be a really basic mistake I made.

3
listprolog
What makes a set a set in your definition? Are you just wanting a list with unique elements? To be a "set" by traditional definition would imply ordering of elements doesn't matter, and that they're all unique. The ordering of elements becomes meaningful only when you consider what operations you want to perform on the set. – lurker
A Set is an algebraic data type whose objects are equipped with a function that given an object tests whether the object is in the Set, or not at O(1). In essence it is a hash map whose keys are unused. A list has O(n) worst case lookup time, and is usually linked by discontiguous allocations that guarantee cache misses. For a set to be a set it MUST be amortized O(1) access time. – Dmitry
"set" is a math concept which has no notion of time. – Will Ness

3 Answers

2
votes

First, there are no sets in Prolog. We have only lists1. So what you can do is to relate a list with duplicate elements to a list without. list_nub/2 would be such a definition.

To your current definition:

Already list2set([], [a]) succeeds, which can't be right. So your definition is too general. You need to replace list2set([],_) by list2set([],[]).

Then, replace member(ListH, Set) by member(ListH,ListT).

And you need another rule for the case where the element is not present:

list2set([] , []).
list2set([E|Es] , Set ) :-
   member(E, Es) ,
   list2set(Es , Set).
list2set([E|Es] , [E|Set] ) :-
   maplist(dif(E), Es),
   list2set(Es , Set).

A more compact definition that avoids redundant answers is list_nub/2.

1) Strictly speaking, one could extend unification via attributed variables2 to implement ACI-unification to have real sets.

2) To my—rough—understanding this would require the implementation of attributed variables in SICStus. Other interfaces like the current in SWI or YAP are most probably insufficient ; as they already are for CLP(B). See this discussion for more.

1
votes

Nice way to populate a unique list, keeping it open-ended.

You can close it with a call length(Set, _), or a hand-coded equivalent (make it deterministic, too), when you're finished:

list2set([], S):- 
    % length( S, _), !
    close_it(S).         % use var/1

Also, consider calling memberchk/2 instead of member/2.

You could also give a "smart" answer, by defining

list2set(X, X).

and saying that you allow duplicates in your representation for sets.

1
votes

Here is a definition that just uses member/2.

% base case
set([], []).
% here we say that if the head is in the tail of the list
% we discard the head and create a set with the tail
% the exclamation mark is a "cut" which means that if member(H, T) was true
% prolog cannot backtrack from set([H|T], X) to set([H|T], [H|X]).
% this prevents giving extra answers that aren't sets, try removing it. 
set([H|T], X):- member(H, T), !, set(T, X).
% and here we say that if the previous clause didn't match because
% head is not a member of tail then we create a set of the tail adding head.
set([H|T], [H|X]):- set(T, X).

Hope it helps!