CODEWITHSUNDEEP
prolog
Rose
Rose

Reputation: 109

Why do these similar programs have different outcomes?

I was doing an exercise that asked to implement from_to/3, where you give two numbers as the first two arguments and Prolog gives you a list of everything between them as result. For example: from_to(1,5,R) would give R=[1,2,3,4,5].

I wrote the following program:

fromto(N, O, []):-
    N >= O.
fromto(N, O, [N|TailResult]):-
    O > N,
    O1 is O-1,
    fromto(N, O1, TailResult).

With query fromto(3,8,R) it returns a list of five 3's. Not good. The correct way to handle it would be:

from_to(N, O, []) :- 
    N > O.
from_to(N, O, [N|TailResult]) :- 
    N =< O, 
    N1 is N + 1, 
    from_to(N1, O, TailResult).

This gives the list 3,4,5,6,7,8 as intended.

My question is how this works. The programs differ only in that I worked down from top to bottom with O and the correct one works upwards by adding to N. Yet the results are totally different. Does anyone know what causes this?

Upvotes: 0

Views: 49

Answers (1)

coder
coder

Reputation: 12972

The problem is that in your first attempt first argument-N does not change only O change, and you place N in the list recursively so all you're gonna see is a list of N's.

If you want to keep this approach you have to place each time O in the list:

fromto(N, O, []):-
    N > O.
fromto(N, O, L):-
    O >= N,
    O1 is O-1,
    fromto(N, O1, L2),
    append(L2,[O],L).

The problem with this implementation is that you need to use append/3in order to place in right order else you will get the inverse list. This is not so efficient because every time you need to add an element in the list you need to traverse all the list and place it at the ende which gives an additional overhead.

EXAMPLE:

?- fromto(3,8,L).
L = [3, 4, 5, 6, 7, 8] ;
false.

Also you could use DCG as suggested by @false:

from_to(N,N) -->[N].
from_to(N,O) --> [N],{N<O, N1 is N+1},from_to(N1,O).

final_solution(N,O,L):- phrase(from_to(N,O),L).

And the other way (decreasing O instead of N):

from_to(N,N) -->[N].
from_to(N,O) --> {N<O, O1 is O-1},from_to(N,O1),[O].

final_solution(N,O,L):- phrase(from_to(N,O),L).

Now the two ways of solving are very similar just change the order of the second clause.

Upvotes: 2

Related Questions