0

I have a problem in the derivation tree of finding the maximum of a given number list. How variables are assigned.?

Following are the rules in Prolog

max([X],X). %If one element list, the element is the maximum

max([X|L],X) :- max(L,M), X > M. %If head is greater than the maximum of tail the head is the maximum.

max([X|L],M) :- max(L,M), X =< M. %If head is less than or equal the maximum of tail, then maximum of tail is the maximum.

So I want to know the steps for how Prolog answer the following query.

?- max([10,20,30], M).

Please give me an idea, how recursive calls work and variables are assigned.

Thank you...

ramesh
  • 19
  • 1
  • 6
  • 1
    Just query `?- trace.` and then do your query. Any answer you get here will be just a more elaborate version of what the trace looks like. –  Nov 25 '15 at 08:33
  • 1
    In Prolog, variables are not *assigned*, but *instantiated*. It's a fundamental difference wrt procedural languages – CapelliC Nov 25 '15 at 09:20
  • @ CapelliC, Can you give me a basic steps about the search tree of max([10,20,30] M). As I'm new to Prolog, my knowledge on this is very very limited. and any disadvantages of the relations I used here?, Thanks... – ramesh Nov 25 '15 at 09:54
  • @Boris give you a very good hint. Sorry but you need to take your time to follow the gory details... or try to follow by hand the execution. That's all... – CapelliC Nov 25 '15 at 11:10
  • The disavantage is that its complexity is quadratic. Clauses 2,3 should be merged, so the recursive call occurs only once. You should choose about the discrimination test. Personally, I would use `max([X|L],M) :- max(L,T), (X>T -> M=X;M=T).` – CapelliC Nov 25 '15 at 11:21
  • Actually, if you have numbers, the predicate could be something like: `max([X|Xs], Max) :- max_1(Xs, X, Max). max_1([], Max, Max). max_1([X|Xs], Max0, Max) :- Max1 is max(X, Max0), max_1(Xs, Max1, Max).` This is the exact definition in the [SWI-Prolog library](http://www.swi-prolog.org/pldoc/doc/usr/lib/swi-prolog/library/lists.pl?show=src#max_list/2). You can also take a look at `max_member/2` defined in the same library. The code you provide is correct, but rather "textbook" than "production". It is annoying that there is a difference, of course. –  Nov 25 '15 at 11:27
  • @CapelliC If you have a list of numbers (or arithmetic expressions of course) you can even avoid the if-then-else by using the `max()` arithmetic function. I did once try to time it and it turned out that if you have only normal numbers (no arithmetic expressions, no rationals) then `max_member/2` is faster than `max_list/2` and still correct. –  Nov 25 '15 at 11:33
  • @CapelliC Thank you very much for the suggestion of optimizing the recursion. So my rules were, maxlist([X],X). maxlist([X|L],M) :- maxlist(L,T), (X>T -> M=X;M=T). @ Boris your idea on "trace" helped me a lot; thank you very much for your information. – ramesh Nov 25 '15 at 19:14
  • @CapelliC: The overhead is **exponential** in the length of the list. See [this answer](http://stackoverflow.com/a/19941560/772868) for more. – false Nov 26 '15 at 17:51

0 Answers0