Comments on predicate that finds the list of elements not shared between two lists (disjoint list)?

Help!
1

I’m using: SWI-Prolog version 8.1.9.

I couldn’t find a predicate in the SWI-Prolog docs that given two lists, gives you a list of all the elements not shared by the two lists. I wrote my own and would like comments on it. Also, if something already existed and I missed it, please link the relevant docs page to me:

	% ----->>>>> gen_disjoint_element_from_lists(+List, +DisjointList, -DisjointElement)
	
	% Description: Generate one element from the given list that is not 
	%	an element of DisjointList.
	gen_disjoint_element_from_lists(List, DisjointList, DisjointElement) :-
		member(DisjointElement, List),
		\+ member(DisjointElement, DisjointList).

	% ----->>>>> try_list_1_or_list_2(+List_1, +List_2, -DisjointElement)
	
	% Description: Generate one element from either list that is 
	%	not an element of the other.
	try_list_1_or_list_2(List_1, List_2, DisjointElement) :-
		gen_disjoint_element_from_lists(List_1, List_2, DisjointElement)
		;
		gen_disjoint_element_from_lists(List_2, List_1, DisjointElement).

	% ----->>>>> disjoint_list(+List_1, +List_2, ?DisjointList)

	% Description: Returns the union list of the elements of 
	%	List_1 not found in List_2, and the elements of List_2
	%	not found in List_1.
	disjoint_list(List_1, List_2, DisjointElementsList) :-
		findall(
			DisjointElement, 
			try_list_1_or_list_2(List_1, List_2, DisjointElement), 
			DisjointElementsList).
2

Being a list a very generic data structure, requirement on list operations should be better detailed. Anyway, I think you’re looking for ord_symdiff/3.

For efficiency, I think memberchk/2 should be used instead of member/2 here

\+ member(DisjointElement, DisjointList).
1 Like
3

Thanks for the link on those two predicates. ord_symdiff is indeed useful, but only if the lists are sorted and my aren’t. I know that you know that. I am pointing it out for other Prolog programmers like myself that happen to find this post who may not know that the ord_ prefixed predicates are for ordered sets, which are by definition sorted and deduplicated:

[debug] 64 ?- ord_symdiff([a, c], [a,d], R).
R = [c, d].
% If the lists are not sorted ord_symdiff can't be used.
[debug] 65 ?- ord_symdiff([c, a], [a,d], R).
R = [a, c, a, d].
4

You can change a list to an ord_set using list_to_ord_set/2 (which simply calls sort/2).
You can remove duplicates from a list (preserving their order) using list_to_set/2.

The semantics of set-like operations on things that aren’t sets can be confusing; also it can be significantly more expensive (I think your code is O(N2) and ord_symdiff/2 is O(N)).

1 Like