3

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.

wsad1000
  • 31
  • 1
  • 2
  • 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 May 04 '16 at 16:40
  • 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. – Dmytro Feb 11 '17 at 09:48
  • "set" is a math concept which has no notion of time. – Will Ness Jan 20 '19 at 23:07

3 Answers3

2

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.

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
2

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!

nicoabie
  • 2,684
  • 1
  • 20
  • 19
1

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.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • "saying that you allow duplicates in your representation for sets" goes against the mathematical definition of a set which is "A collection of distinct objects, considered as an object in its own right" – nicoabie Jan 20 '19 at 19:38
  • no, it is just a question of interpretation. a list `[2,2,4]` can serve as a representation of set `{2,4}`. there's no problem there. the problem of multiplicity never arises because that question is never asked about a set, by definition. membership works just the same. union too. set difference will need to be implemented in a specific way taking this into account. so it will be more involved, different than with the unique elements list representation. – Will Ness Jan 20 '19 at 22:43