How do I get the shortest list from all the unified options for a list variable in prolog?

Question

So I'm trying to get the shortest path between two nodes in a tree. I have the predicate path(Start,End,Path) that unifies Path to be all the possible routes from Start to End. Since I want the shortest route I want to get the shortest Path. How am I supposed to "cycle" through all the options that Path can get? Thank you

Answer 1

A somewhat more "classical" answer would be to use one of the extralogical predicates setof/3, bagof/3 and findall/3. setof/3 in particular can be repurposed to calculate minima through a neat trick, but setof/3 and bagof/3 can somewhat counterintuitively return more than once depending on whether the internal variables are existentially quantified or not.

Suppose we're using the classic Biblical paternity database. We could have:

father(abraham, isaac).
father(isaac, jacob).
father(jacob, joseph).
father(jacob, benjamin).

and so forth. Suppose you want the list of fathers. This is one way:

?- findall(Father, father(Father, _), Fathers).
Fathers = [abraham, isaac, jacob, jacob].

But then you notice that jacob is in there twice. You think, I know, I'll use setof/3. Then you get this:

?- setof(Father, father(Father, _), Fathers).
Fathers = [jacob] ;
Fathers = [abraham] ;
Fathers = [isaac] ;
Fathers = [jacob].

What happened here is Prolog is unifying _ with some value, and that value is constraining the result. In other words, jacob is present twice because he has two kids, and each one is a separate binding for the _. The solution is to specify existential quantification with some special syntax:

?- setof(Father, Child^father(Father, Child), Fathers).
Fathers = [abraham, isaac, jacob].

The Child^ syntax there is a way of telling Prolog: there is some value that binds this variable, but I don't care what it is, I don't want my result constrained by it. This way we get the expected result.

So now we can get all the solutions to path(Start, End, Path) in one place:

?- findall(Path, path(Start, End, Path), Paths).

In case you're having trouble reading that, what we're saying is "find all Path bindings in the expression path(Start, End, Path), and gather them up into a new variable Paths."

From here, we can just treat this like any other list and find the minimum by sorting or scanning through the list by hand, or both, or whatever.

I mentioned before we can sometimes trick setof/3 into doing minimization. If you're confident path/3 will terminate in a reasonable amount of time—in other words, that findof/3 applied to path/3 will not produce an infinite loop—we can do the following trick:

setof((Len,Path), (path(Start, End, Path), length(Path, Len)), [(_,ShortestPath)|_]).

Indulge me for just a second more. Earlier when I mentioned the first argument of setof/3 is the variable to find, it's really an expression that is unified with each successful result of the second argument. So we're saying to collect both the Len and Path variables in an expression (Len,Path). Note: this is not a tuple! This is just an expression build using the ,/2 operator. I am more inclined to write it like this:

setof(Len-Path, (path(Start, End, Path), length(Path, Len)), [_-ShortestPath|_]).

There's no difference between using Len-Path or (Len,Path) or any other syntax to combine Len and Path. The important thing is that they're in some expression—any expression—together. Prolog won't automatically do arithmetic with -/2 and it won't automatically "and" things together with ,/2 so we're free to do this. The other important detail is that we need the length to go first, because that's what setof/3 is going to sort on.

The third argument looks really terrible, so let's break it down:

[(_, ShortestPath)|_]   % or: [_-ShortestPath|_]

This is just a pattern nested within a pattern. We know there will be at least one result, so we're using the list pattern [Head|Tail] here. It's just that we don't care about the tail, so we have [...|_], so we're taking apart the first element of the list. Then we know that every item in this list is going to have the structure (Len, Path) from the first clause. So what we're doing here is expecting to get a result that looks like:

[(3, <path>), (4, ...), (5, ...), ...]

and we just want to get <path> out of the first element.

Note that we don't have to handle other cases because if there are no solutions, we should fail anyway!

Now all that said, if you have access to a library like aggregate that will do this work for you, by all means use that instead. I mainly think it's instructive to know what one's options are. (This seto/3 trick comes from the book Prolog Programming in Depth by Covington et. al.).

Edit: On walking the solutions list directly

One of the nice things about Prolog--maybe even the nice thing--is that with backtracking it will generate all the solutions. This makes it pretty straightforward to write minimization queries, for instance:

age(abraham, 103).  age(isaac, 45).
age(jacob, 88).     age(joseph, 46).

youngest(Person) :-
    age(Person, Age),
    \+ (age(_, Younger), Younger < Age).

What's being stated there logically is: the youngest person is the person Person with age Age such that there is no other person with age Younger less than Age. This is a really cute way to do the problem; the problem is that it has to traverse the entire database for each fact until it finds a solution. It's tragically inefficient.

In order to do it more efficiently we have to resign ourselves to being a little more explicit about what we want to do. Now, the next most-explicit and possibly clearest solution is to use findall/3 to generate all the possibilities and then select the right one by recursively processing the list. The code could look like this:

youngest(Youngest) :-
    findall((Person, Age), age(Person, Age), [(FirstPerson,FirstAge)|People]),
    youngest_loop(FirstPerson, FirstAge, People, Youngest).

youngest_loop(Youngest, _, [], Youngest).
youngest_loop(CurrentPerson, CurrentMinimumAge, [(NextPerson,NextAge)|People], Youngest) :-
    (   (CurrentMinimumAge > NextAge) ->
        youngest_loop(NextPerson, NextAge, People, Youngest)
    ;   youngest_loop(CurrentPerson, CurrentMinimumAge, People, Youngest)).

The first rule is simply converting the fact database into a list of pairs, and the second rule is processing that list in the expected way, by carrying along the current minimum and comparing each one to the current minimum to decide if it replaces it or not. Depending on what you're doing this may be more efficient or less, but that's a bigger topic.

Note: setof/3, bagof/3 and findall/3 are standard Prolog and should be available everywhere. This isn't a library routine so much as a built-in.

Now, about the strange-looking behavior with a callable goal in the middle. There's actually no magic going on here, it's just regular unification. You can demonstrate this yourself by writing a similar looking predicate, say one that calls a goal repeatedly with numbers like a loop:

loopy(Start, Stop, Var, Goal) :-
    numlist(Start, Stop, Numbers),
    member(Var, Numbers),
    Goal.

?- loopy(1, 10, X, (write('Generating '), write(X), nl)).
Generating 1
X = 1 ;
Generating 2
X = 2 ;
...etc...

By taking Var and Goal together we were able to establish a binding for Var using member/2 and then ask Prolog to "prove" Goal. Goal could have been any Prolog expression, so the parenthesized expression there "just worked". It's important that Var match the variable used in Goal though, or you get this strange-looking behavior instead:

?- loopy(1, 10, Y, (write('Generating '), write(X), nl)).
Generating _G811
Y = 1 ;
Generating _G811
Y = 2 ;
...etc...

Hope this answers your questions!

Answer 2

you can use library(aggregate).

shorter_path(Start, End, MinPath) :-
   aggregate(min(Len, Path),
     (path(Start, End, Path), length(Path, Len)),
     min(Len, MinPath)).