1

So I have an assignment to work on and there is one thing I'm confused about. Here is a similar problem to what I'm trying to accomplish. Say I have these rules:

size(3).
size(5).
size(7).
size(1).
size(2).
size(9).

And I want to find the minimum of size by taking the value 3 and comparing it to 5, storing 3 and comparing it to 7, then comparing it to 1, storing 1 and comparing it to 2...returning a value of 1.

The only way I can see of doing that without a high order procedure would be some form of backtracking while there are still size(X) values and each time altering the size variable. However, I don't see how you can both backtrack and save the new minimum value. I was wondering if anyone could help put me on the right track.

false
  • 10,264
  • 13
  • 101
  • 209
Joseph Kahn
  • 396
  • 1
  • 3
  • 16

1 Answers1

3

your assignment is intended to make you thinking about the peculiar control flow of Prolog, and indeed you are now to the point. I've coded the solution and placed some explanatory comment: fill in the ellipsis to complete the code

find_min_size(MinSize) :-
    size(Hypothesis),
    !,  % without this cut the minimum is obtained more times...
    find_min_size(Hypothesis, MinSize).

find_min_size(SoFar, MinSize) :-
    % when I should keep searching?
    ...

% the exhaustive search come to end!
find_min_size(MinSize, MinSize).

I don't think in Prolog is possible to get O(N) performance, without 'higher order procedures' ( do you mean findall etc..? ). The code above will run in O(N^2). Indexing can't play a role, because size/1 will restart with unbound variable...

An interesting O(N) alternative is using a failure driven loop and the tech that @false explained so well when introducing call_nth, (also, see here a follow up). All of these are in the 'impure' realm of Prolog, though...

edit here the failure driven loop

find_min_size(MinSize) :-
    State = (_, _),
    (   size(V),
        arg(1, State, C),
        ( ( var(C) ; V < C ) -> U = V ; U = C ),
        nb_setarg(1, State, U),
        fail
    ;   arg(1, State, MinSize)
    ).
Community
  • 1
  • 1
CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • Hmm.. Don't quite understand how this should work. Each `size(X)` will split search tree into N different values of `X`. In your `find_min_size/1` you take only first variant and cut-off rest. As I understand `find_min_size/2` should be recursive and pass with new `SoFar` till the moment there is no `size/1` left. But how would you convert parallel branches of `size/1` into sequence? Even if you'll define `find_min_size(H, M):- size(H1), H1 < H, !, find_min_size(H1, M).` you still actually iterate over all `H1` variants and filter those that improve solution. – ony Nov 27 '12 at 13:54
  • it's very easy: size(X) just restart, but the condition filter out unwanted (again!) -> it's O(N^2) – CapelliC Nov 27 '12 at 14:33
  • I'm trying to say that "indexing" and [tabling](http://www.dcc.fc.up.pt/~vsc/Yap/yap.html#Tabling) will not help anyway since new `SoFar` will not match with any previous "calls". – ony Nov 27 '12 at 14:50
  • Yes, I understood, and edited the answer. That code it's O(N^2). Now I'm working on the call_nth path... – CapelliC Nov 27 '12 at 14:52
  • @CapelliC: Can't you offer a **generic** solution? nb_setarg/3 should not be spread around user code but rather confined to general library code. – false Nov 27 '12 at 19:19
  • @false: yes, but the requirement 'without high order procedures' made me to avoid call/N... – CapelliC Nov 27 '12 at 20:02
  • @CapelliC: Everytime nb_* is abused, Prolog loses. – false Nov 27 '12 at 20:04
  • @false: I must admit I don't know a way to solve the problem in O(N) other than with nb_... – CapelliC Nov 27 '12 at 20:06
  • @CapelliC: Not every requirement stated by OP makes sense. "without high order procedures" That's just nonsensical to demand. – false Nov 27 '12 at 20:09
  • @false: for a **generic** solution, I'll attempt to optimize aggregate_all, and if I'll succeed, then place as a pack on SWI-Prolog site. – CapelliC Nov 27 '12 at 20:16
  • " Not every requirement stated by OP makes sense. "without high order procedures" That's just nonsensical to demand." I stated it was for homework, I didn't think it made sense. Given what the requirements say on the sheet I'm going to assume the first solution is what was intended. The reason I asked about it in the first place was that I didn't know if it was even possible to do it the way I said given how I understood prolog. CapelliC, thank you :) – Joseph Kahn Nov 27 '12 at 21:27