Why won't my Prolog distance function work?

1
votes

This is what I have.

distance([],[],0).
distance([V1|T1],[V2|T2], sqrt((V1-V2)^2 + D2)):-
   distance([T1],[T2],D2).

It gives the out of global stack error. I also tried:

distance([V],[V],0).
distance([V1|T1],[V2|T2], D):-
   D2 is distance([T1],[T2],D2),
   D is sqrt((V1-V2)^2 + D2).

and it says that arguments are not sufficiently instantiated.

I'm trying to calculate sqrt((x1-y1)^2 + ... + (xn-yn)^2).

edit:

This is what I have now, it hangs up now.

distance([],[],0).
distance([X1|X2],[Y1|Y2],D):-
   distance([X2],[Y2],D2),
   D is sqrt((X1-Y1)^2 + D2).

edit:

I've got working now, thanks. This is my solution.

sumd([],[],0).
sumd([X|X2],[Y|Y2],D):- sumd(X2,Y2,D2), D is (X - Y)^2 + D2.

distance([X|X2],[Y|Y2],D):- sumd([X|X2],[Y|Y2],S), D is sqrt(S).
2
prolog
In your new, edit solution, as @PauloMoura points out, you have an incorrect syntax for a list head and tail. The list [X1|X2] represents a head element, X1, and a tail list, X2. So your recursive distance query should be distance(X2, Y2, D2). That will fix your hang-up since, as it stands now, the first to arguments will never "drive" to [] since you always make a list of one element out of them. Your second issue will be your computation, you're going to have distance = sqrt((x1-y1)^2 + sqrt((x2-y2)^2 + sqrt(...))) when it's done (nested square roots). - lurker

2 Answers

2
votes

In a nutshell, Prolog is not a functional language. Thus, in your first version of the distance/3 predicate, the term sqrt((V1-V2)^2 + D2) is never evaluated as an arithmetic expression. In your second version, you cannot use the standard built-in predicate is/2 with distance([T1],[T2],D2), which will not be recognized as an arithmetic expression (in standard Prolog, you cannot define your own arithmetic functions). Can you now fix the problem given this information and post back your new definition for the distance/3 predicate?

1
votes

Now that you have a working solution (and that's always the first step), you can consider improving it. You have a predicate, sumd/3 defined using recursion using two clauses: a base clause, which is used when either the input lists are empty or when you finished traversing the input lists using the general, recursive, clause. But there's a problem: the recursive call, sumd(X2,Y2,D2), is not the last call in the clause body. The practical consequence is that the sumd/3 predicate requires space proportional to the length of the input lists as every time a recursive call is made, the following goal, D is (X - Y)^2 + D2, needs to be saved as it will only be proved after the recursive call is proved. Internally, the D is (X - Y)^2 + D2 goals are saved in a stack. The solution is to use a tail-recursive definition, i.e. a definition where the recursive call is the last one in the clause body. This can be easily accomplished using an additional argument that will play the role of an accumulator. The idea is to use this argument to accumulate the partial results as you traverse the input lists. When you reach your base case, i.e. when you finish traversing the input lists, the accumulated value would be the final value. The first clause is simple and is used to initialize the accumulator. Given that we'll be accumulating a sum, the initial value will be zero:

distance(List1, List2, Distance) :-
    distance(List1, List2, 0, Distance).

Now the base case for our distance/4 auxiliary predicate, Taking into account the explanation above:

distance([], [], Distance, Distance).

Can you now write yourself the recursive case?

distance([X| Xs], [Y| Ys], Distance0, Distance) :-
    ...

Note the Distance0 represents the value accumulated so far.