CODEWITHSUNDEEP
listprolog
wsad1000
wsad1000

Reputation: 31

Creating a set from a list in Prolog

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.

Upvotes: 3

Views: 7831

Answers (3)

nicoabie
nicoabie

Reputation: 2894

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!

Upvotes: 2

false
false

Reputation: 10142

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.

Upvotes: 2

Will Ness
Will Ness

Reputation: 71119

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.

Upvotes: 1

Related Questions