Intersection_chk/2

Nice to know
, , ,
1

As Jan W. notes below, one should use ordered sets and then use ord_intersect/2 instead of the following code. :dizzy_face:

intersection_chk(A,B) :-
    member(Item,A),
    memberchk(Item,B), !.

Many Prolog programmers know of member/2 and less know of memberchk/2.
Some know of intersection/3 and ord_intersection/3 but there is no intersection_chk/2, thus posted.

In checking thousands of sets against each other there was no need for the full intersection but only the fact if the two sets have at least one item in common. I think of this as a short circuit evaluation, why do all of the checks if you can stop when you find one that succeeds.

As I have often noted, correctness comes before performance. In this case to get a correct result requires converting the list to ordered sets using list_to_ord_set/2 and then using ord_intersect/2 instead of the posted code above.

Test cases 
:- begin_tests(my_set).

:- use_module(my_set).

intersection_chk_test_case(01,[               ],[           ],false ).
intersection_chk_test_case(02,[a-1            ],[           ],false ).
intersection_chk_test_case(03,[               ],[a-1        ],false ).
intersection_chk_test_case(04,[a-1            ],[a-1        ],true  ).
intersection_chk_test_case(05,[a-1            ],[b-1,c-1,a-2],false ).
intersection_chk_test_case(06,[a-1,b-2,c-2,d-1],[b-1,c-1,a-2],false ).
intersection_chk_test_case(07,[a-1,b-2,c-2,d-1],[a-1,c-1,a-2],true  ).
intersection_chk_test_case(08,[a-1,b-2,c-2,d-1],[b-1,a-1,a-2],true  ).
intersection_chk_test_case(09,[a-1,b-2,c-2,d-1],[b-1,c-1,a-1],true  ).
intersection_chk_test_case(10,[a-1,b-2,c-2,d-1],[b-2,c-1,a-2],true  ).
intersection_chk_test_case(11,[a-1,b-2,c-2,d-1],[b-1,b-2,a-2],true  ).
intersection_chk_test_case(12,[a-1,b-2,c-2,d-1],[b-1,c-1,b-2],true  ).
intersection_chk_test_case(13,[a-1,b-2,c-2,d-1],[d-1,c-1,a-2],true  ).
intersection_chk_test_case(14,[a-1,b-2,c-2,d-1],[b-1,d-1,a-2],true  ).
intersection_chk_test_case(15,[a-1,b-2,c-2,d-1],[b-1,c-1,d-1],true  ).

test(intersection_chk,[true,forall(intersection_chk_test_case(_Index,A,B,true))]) :-
    intersection_chk(A,B).

test(intersection_chk,[fail,forall(intersection_chk_test_case(_Index,A,B,false))]) :-
    intersection_chk(A,B).

:- end_tests(my_set).
2

As the example at intersection/3 named What is wrong with intersection/3 and friends? explains, the set manipulation based on unification is dubious. If you need sets, use library(ordsets). That has ord_intersect/2 which just tests that two sets intersect.

Alternatively you may choose for hash tables balanced trees to represent sets, depending non what you need to do with them.

1 Like
3

Should we leave this topic up or delete the entire thing and I can post a new topic in Nice to know?

4

I more extensive discussion on how to deal with sets is more useful. An intersectionchk/2 is useful if you do sets the wrong way :slight_smile:

1 Like