Allowing ord_del_element on non-ground compound terms?

Request For Comments
1

ord_del_element/3 won’t delete a term when the query element is not ground. This is based on the way that the library uses compare/3. I’ve written an alternative that tries unification first, but I’m not sure if I’m missing some technical reason why that might be a bad idea.

An example of the issue,

:- ord_del_element([f(1),g(2),h(3)],g(X),R).
R = [f(1), g(2), h(3)].

Here, ord_del_element doesn’t delete the element because the query term is greater than the list term. In contrast, if the query element is ground, then the query term would be deleted.

:- ord_del_element([f(1),g(2),h(3)],g(2),R).
R = [f(1),  h(3)].

The library code that ord_del_element uses is the following:

%% oset_delel(+Set, +El, -Del)
%   ordered set element deletion

oset_delel([], _El, []).
oset_delel([H|T], El, Del) :-
    compare(Order, H, El),
    delel(Order, H, T, El, Del).

delel(<,  H, T,  El, [H|Del]) :-
    oset_delel(T, El, Del).
delel(=, _H, T, _El, T).
delel(>,  H, T, _El, [H|T]).

The following modification (renamed so that I don’t interfere with the library code), would address the issue. I try unification first to see if a term matches. If a term doesn’t match, then proceed with the order comparison. If the query term is greater than the next list term, then terminate (thus keeping the performance benefit of an ordered list).

% ordered set delete that allows unification
%% ord_delel(+Set, +El, -Del)
%   ordered set element deletion

ord_delel([], _El, []).
ord_delel([H|T],H,T).
ord_delel([H|T], El, Del) :-
    compare(Order, H, El),
    delel(Order, H, T, El, Del).

delel(<,  H, T,  El, [H|Del]) :-
    ord_delel(T, El, Del).
delel(>,  H, T, _El, [H|T]).
2

Design choices. When deleting an element from e.g. a set or a list, we need to compare elements. This can be accomplished using either term equality or term unification. With term unification, we still need to decide if we carry the bindings of an unification to the next comparisons. Libraries with a delete operation usually make the choice clear in the documentation.

3

… And, although I’m not sure, I suspect that the proposed solution goes wrong in some cases because unification may change the standard order of non-ground terms. There have been earlier discussions on standard order of term and unification. Bottom line is more or less that one should either make sure the terms are ground or know what you are doing as these operations are important at the moment you need to process variables in some other way than the default SLD resolution.

Delete (see delete/3) is anyway very hard to define. Note the use of \+ Elem \= Head in the docs!