In my head (don’t know if there is any correspondence to reality) instead of calling a predicate in the body of a rule such as desirable(Item) or undesirable(Item), using some kind of “matching” in the head of the rule itself would make things more efficient, like the following:
From the point of view of the user of the predicate, the name doesn’t really tell me what it does (desirable is hidden in the definition, rather than the predicate being named desirable_subset), so its a bad example. However I’m not sure of why you think desirable(Item) is evaluated in your second example, it isn’t. However, trying to move the filter logic outside the predicate is what the include/3 and exclude/3 predicates do.
e.g.
That’s the predicate O’Keefe himself uses to abstract from any given predicate one might be interested in…his starting point is the so-called Dutch National Flag problem in which items should be arranged based on their color (in that case the predicates would be red(Item), white(Item) and blue(Item). The general question was whether avoiding to call predicates in a rule’s body and using pattern-matching in the rule’s head is generally more efficient or not…my guts feeling, so to say, tends to say yes, but I was hoping in an answer from the experts
Please try it out. The textbook solution and your proposed alternative are different in meaning. It will become obvious if you programmed a small concrete example. If the results surprise you please ask us, the readers of your messages, for further help.
So possibly I’ll have to use a big list of items and time the two alternatives to see if there’s (or there isn’t) a significant change in terms of performance
I ran the same trace and list on O’Keefe’s script (I can only embed one picture), and the initial call was exactly the same so it looks like the initial call structure of ?- subset(Item,Items). results in the same initial call.
I would recommending defining desirable/1 and undesirable/1 in both scripts and testing it on short lists, as others have recommended. Please let us know how it goes!
Well as a side observation: today tracing some queries with @peter.ludemann’s definition for subset_on_condition I was surprised to see how the not provable predicate (\+) is traced:
\+ red(store) should succeed, right? I don’t know, I don’t find the trace particularly clear in this respect…but this is a side observation. I’ll try to understand things better for the general matter.
PS: the trace doesn’t make clear that the first time red(store) is called, but the second time \+ red(store) is called
“Let’s take the case of finding blue items. There is one way that an item can be desirable: it can be blue. There are two ways it can be undesirable: it can be red or it can be white”
Version 1
Now my question doesn’t have to do with the Dutch National Flag problem, but rather (a classic) with choice points. In Version 1 we have three clauses, in Version 2 four ones. Does it make a difference relative to the choice points left? Because if it does, then Version 1 would leave fewer choice points and would be therefore more deterministic than Version 2? Thanks
There will be slightly different choice points between Version 1 and Version 2. Version 2 will leave a choice point after the head in the 3rd clause; Version 1 will leave a choice point at the semi-colon in red(Item);white(Item). You should be able to see this if you trace the code.
