CODEWITHSUNDEEP
prolog
heisenberg7584
heisenberg7584

Reputation: 740

Member (extended) predicate - find element in a list of lists (any level)

We all know the classic Prolog predicate for member:

member(X, [X|T]).
member(X, [Y|T]) :- member(X,Y).

I am struggling to come up with the extended member predicate which i searching for an element in a list of lists (of lists and so on...). For example:

member(4, [1,2,[3,4,[5]],[6,7,9]]).
TRUE

Upvotes: 1

Views: 343

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

We can define such predicate by three rules. X is a member of a list L given L is a non-empty list with:

  1. X is its first element;
  2. X is a member of its first element (which is therefore a list as well); or
  3. X is a member of the rest of the list (its "tail").

With these three conditions, we can write a predicate rmember/2 (recursive member) for example:

rmember(X, [X|_]).    %% (1)
rmember(X, [H|_]) :-  %% (2)
    rmember(X, H).
rmember(X, [_|T]) :-  %% (3)
    rmember(X, T).

The first and third condition are also present in a simple member/2 predicate, only the second condition is "unique" to a recursive membercheck.

We can slightly improve the efficiency of the above, by making a predicate with three parameters, with the tail of the list the first one, the element to search the second one, and the head of the list the third one. This is a popular approach like for example SWI-Prolog's member/2 implementation [swi-doc].

The advantage of this is that we avoid unpacking the list multiple times. We can also restrict the pattern of the second case, such that this is only called for non-empty sublists:

rmember_(_, El, El).
rmember_(_, El, [H|T]) :-
    rmember_(T, El, H).
rmember_([H|T], El, _) :-
    rmember_(T, El, H).

we can then define rmember/2 in terms of _rmember/3:

rmember(X, [H|T]) :-
    rmember_(T, X, H).

Upvotes: 3

Related Questions