3

I would like to know if it's a good idea to get the max value (oldest person) of some facts via backtracking like this:

data(MaxID, MaxName, MaxAge),
\+ (data(ID, Name, Age), ID \= MaxID, MaxAge < Age).

Or vice versa for the min value (youngest person):

data(MinID, MinName, MinAge),
\+ (data(ID, Name, Age), ID \= MinID, MinAge > Age).

Is this efficient in terms of space or time complexity?

Is the implementation's style easy/straightforwarded? Do "nicer" implementations exist?

false
  • 10,264
  • 13
  • 101
  • 209
daniel451
  • 10,626
  • 19
  • 67
  • 125

2 Answers2

2

Is this efficient in terms of space or time complexity?

Your implementation it's O(N^2) wrt time complexity, since for each candidate predicate all others gets 'called upon' for comparison. Space complexity is O(1).

Do "nicer" implementations exist?

Yes, nicer and more efficient implementations exist. Long time now, SWI-Prolog offers library(aggregate), a straight enhancement to setof/bagof/findall classical builtins:

?- aggregate(max(Age,data(ID,Name,Age)), ID^Name^data(ID,Name,Age), max(_,X)).

Note the style of quantification control expressed by ID^Name^.... It's the very same required by setof/3 and bagof/3. The implementation is more efficient tough, based on non backtrackable assignment.

The latest addition to could be considered library(solution_sequences). Before digging inside this last one, consider exercising library(aggregate).

edit

Based on @false comment to the question, and the answer @boris, I would try to provide a 'nicer' (of course, a subjective evaluation) implementation:

min(P,A) :-
    copy_term(P,Q),
    arg(A,P,V), arg(A,Q,U),
    call(P), \+ ( call(Q), U@<V ).

now, you can pass your predicate as first parameter, and specify the argument of P to be used for comparison with the second parameter.

CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • 1
    Downside of library(aggregate): Breaks constraints. What about the other one? – false Mar 04 '17 at 20:29
  • Talking about your edit only: another "nice" thing (very subjective) would be if library(aggregate) would be able to do the equivalent of a foldl without building a list. At the moment it does it only for a hard-coded set of aggregate functions: count, min, max. At least this is what I get from looking at the code. –  Mar 05 '17 at 10:56
0

The short answer is, no, nothing really "nicer" exists, in terms of being always correct, easy to implement, and efficient all at the same time.

A small correction: it is enough to write

data(MaxID, MaxName, MaxAge),
\+ (data(ID, Name, Age), MaxAge < Age)

(as suggested by @false in the comment to your question)

You can see also this question and answers. This answer goes into some detail when and why using setof/3 can be problematic. It might be important for your use case.

Another way to do it (not mentioned in the very useful answer by @CapelliC) is to collect all solutions from your predicate and sort them, using a key. If you are using SWI-Prolog, or another Prolog that has the 4-argument version of sort that lets you choose the comparison and the key within a term, you could do, for example:

bagof(data(ID, Name, Age), data(ID, Name, Age), All),
sort(3, @>=, All, [data(Max_ID, Max_Name, Max_Age)|_])

As long as your data/3 is just a table of facts, this is safe to use.

This of course breaks down if you have equivalent but not equal elements in the list, as data(10, john, 34) and data(101, jane, 34). In the question and answer I linked there are examples how to deal with this, but again, I really don't think it gets any "nicer". It could be more efficient. I strongly recommend considering your use case carefully, and measuring performance if you think this can be a bottle neck.

Looking into the implementation of library(aggregate) suggested by @CapelliC it is obvious that it was meant for that use case exactly: it can find minimum, maximum, sum and so on in constant memory and touching each fact only once, and falls back to building the whole list if necessary.

Community
  • 1
  • 1
  • 1
    Of course, library(aggregate) shows its usefulness when you need to *aggregate*. Sum cannot be solved in the same OP's style. Then, isn't *nicer* to have a single syntax to learn covering *all* (well, more or less) the aggregation functions that SQL offers ? – CapelliC Mar 05 '17 at 10:42
  • @CapelliC Absolutely, I was trying to compare doing it manually with bagof or findall to using library(aggregate). –  Mar 05 '17 at 10:50
  • I don't get exactly what you mean... by all metrics, having to write a program, even a dumb one as the one we're discussing, seems to be a less good choice WRT learning to use a library. Isn't this a basic property of *all* SW today ? – CapelliC Mar 05 '17 at 10:54
  • @CapelliC Now I am not sure if I understand what you mean. If you mean that learning to use libraries is more useful that doing things yourself, well, yes, but choosing libraries requires the kind of understanding that you get from doing it yourself. Or did I miss your point? –  Mar 05 '17 at 10:58
  • 1
    If this (`from doing it yourself`) would be true then no good library could exist :) – CapelliC Mar 05 '17 at 11:00
  • @CapelliC Ha, sure, maybe "trying to do it yourself and failing"? But in all seriousness, if you learn how to program without ever trying to reimplement library functionality, you would end up with a very specific and somewhat limited skill set. –  Mar 05 '17 at 11:48