Member

The predicate member/2 is commonly used for either searching a list for a particular element or generating all elements of a list using backtracking. Analogous operations are also useful for other data structures, though searching is often best treated separately for efficiency reasons. To generalise member/2 we noted that it can succeed with non-lists, since solutions can be returned without the whole data structure being traversed. In our transformation all non-recursive calls are simply deleted. We add one extra argument which is bound to successive members of the data structure; there are no ``higher order'' arguments added. Conjunctions of calls are transformed into disjunctions, with the same variable used as the extra argument in the head and each call. Additional disjuncts are added which unify this variable with each variable which occurs in the clause head but not in a recursive call. Clauses with no recursive calls or head variables have fail (an empty disjunction) as the body; such clauses could also be deleted. Program 19 shows the result of transforming rtree_any/1.

member_rtree_any(rt(A, B), C) :-
    (    C = A
    ;    member_list_rtree_any(B, C)
    ).

member_list_rtree_any([], A) :-
    fail.
member_list_rtree_any([A|B], C) :-
    (   member_rtree_any(A, C)
    ;   member_list_rtree_any(B, C)
    ).

Program 19: Member transformation for rtree_any/1