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
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