3

How will Prolog respond to the following inquiry? Draw a search tree for the inquiry, too.

?- member(2, [2, a, X]).

So first of all, what does this inquiry mean?

Let's take another more clear example:

?-  member(vincent,[yolanda,trudy,vincent,jules]).

Prolog will check if vincent is in the list. It checks one by one, so it will first compare vincent and yolanda. No match, now recursive rule aka go to second clause. Now it looks like that:

?-  member(vincent,[trudy,vincent,jules]).

vincent and trudy, no match. Recursive rule:

?-  member(vincent,[vincent,jules]).

vincent and vincent, match! So return true.

Back to our example. Prolog will immediately return true as 2 is in the list (namely the head of it).

But how will the search tree look like? I really have no idea and I'm scared they will ask me to draw a search tree in the test...

false
  • 10,264
  • 13
  • 101
  • 209
eyesima
  • 215
  • 4
  • 15

1 Answers1

5

That query means

For which X is 2 an element of the list [2, a, X]?

Well, let's see how Prolog answers this:

?- member(2, [2, a, X]).
   true
;  X = 2.

The first answer we get is true which is the empty answer substitution. It means here that 2 is a member of that list for any X. Really any! Can this be true?

?- X = any, member(2, [2, a, X]).
   X = any
;  false.                % that is no solution

It's even true for any!

Now back to the original query: The second answer is a simple solution X = 2. So Prolog tells us that also 2 might be such an element. Alas, we already know that, for we know that this holds for any term. And thus also 2. Therefore, the second answer is redundant.

You can avoid many such redundancies by using memberd/2 instead!

As for the search tree, member/2 always visits the entire list. One solution after the other. So the search tree only depends on the number of elements in the list.

false
  • 10,264
  • 13
  • 101
  • 209