Matching Multiple Lists

Question

Hi there,

I can write a predicate that is satisfied when two lists are equal e.g. equal([2,3],[2,3]) would be true and equal([2,3],[4,5]). would be false.

However, what if I want to have a list and try and match it with any list in a list of lists e.g. match([2,3],[[5,6],[4,6,2],[2,3]]). would be true because of the last list in the list of lists but match([2,3],[[3,4],[4,2,1]]). would be false because [2,3] doesn't match anything in the list of lists.

I'm thinking maybe we might need nested recursion here? Any idea how you do this? The problem I'm trying to solve is much larger but just being able to do this would allow me to solve the whole problem.

Thanks in advance.

Answer 1

Recursive navigation of a Prolog list is usually achieved by means of a couple of clauses: the first is the condition by which the recursion is stopped and a result is returned; the second contains the recursive call. To this aim, in each clause's head the list on which the recursion has to be performed is typically broken in two parts, isolating the first element (known as head) from the rest of the list (known as tail), such as in the following:

p(Element, [Head | Tail]) :- % ...

In that recursive clause, you process Head and, depending on the result, you proceed to call your predicate passing Tail as second argument, thus actually navigating the whole list one element at a time.

In writing such a predicate, you may cut (using !) alternative solutions (that sometimes produce only failures) when you find the result you were looking for, e.g. in your case, once you find a match between the first list and an element in the second list, you don't need to proceed further, so any possibly open branch in the demonstration tree should be pruned.

Answer 2

UPDATE: I was imagining things were more complicated because of the nested list but something as simple as this actually works:

 match( Search, [H|_] ) :-
    Search = H, !.
match( Search, [H|T] ) :-
    Search \= H,
    match( Search, T ).

Giulio, your answer was very helpful so thanks :).