CODEWITHSUNDEEP
prologtail-recursion
SEPS
SEPS

Reputation: 105

Tail-recursive program in prolog which outputs odd numbers in a list

I've written a tail-recursive predicate in Prolog which outputs the integers between A and B in a list K. I've used "reverse" to bring the numbers into the right order:

numbers(A,B,K) :- numbers(A,B,[],K).
numbers(Y,Y,X,K) :- !, reverse([Y|X],K).
numbers(A,B,X,K) :- A<B, C is A+1, numbers(C,B,[A|X],K).

Query:

?- numbers(3,6, K).
   K=[3,4,5,6]

All works fine. What I now want to do is that I only want to have odd numbers of the range between A and B in the list K. How can I do that? Thanks in advance!

Upvotes: 1

Views: 683

Answers (3)

joel76
joel76

Reputation: 5675

Another possibility is to use DCG :

numbers(A,B,K) :-
    phrase(odd(A,B), K).

odd(A,B) --> {A > B, !}, [].

odd(A,B) --> {A mod2 =:= 0, !, C is A+1}, odd(C,B).
odd(A,B) --> {C is A+2}, [A], odd(C, B).

Upvotes: 1

lurker
lurker

Reputation: 58244

Firstly, I would try to avoid using reverse/2. If you have such a solution, it's often an indicator that there's a better way to get the answer forwards more directly. Not always, but most often. reverse/2 is probably the 2nd favorite band-aid in Prolog right behind use of the cut. :)

In many problems, an auxiliary accumulator is needed. In this particular case, it is not. Also, I would tend to use CLP(FD) operations when involving integers since it's the more relational approach to reasoning over integers. But you can use the solution below with is/2, etc, if you wish. It just won't be as general.

numbers(S, E, []) :- S #> E.   % null case
numbers(X, X, [X]).
numbers(S, E, [S|T]) :-
    S #< E,
    S1 #= S + 1,
    numbers(S1, E, T).

| ?- numbers(3, 8, L).

L = [3,4,5,6,7,8] ? ;

no
| ?- numbers(A, B, [2,3,4,5]).

A = 2
B = 5 ? ;

no
| ?-

This solution avoids reverse/2 and is tail recursive.

To update it for odd integers, the first thought is that we can easily modify the above to do every other number by just adding 2 instead of 1:

every_other_number(S, E, []) :- S #> E.
every_other_number(X, X, [X]).
every_other_number(S, E, [S|T]) :-
    S #< E,
    S1 #= S + 2,
    every_other_number(S1, E, T).

| ?- every_other_number(3, 7, L).

L = [3,5,7] ? ;

no
| ?- every_other_number(3, 8, L).

L = [3,5,7] ? ;

no
| ?- every_other_number(4, 8, L).

L = [4,6,8] ? ;

no
| ?-

Then we can do odd numbers by creating an initial predicate to ensure the condition that the first value is odd and calling every_other_number/3:

odd_numbers(S, E, L) :-
    S rem 2 #= 1,
    every_other_number(S, E, L).
odd_numbers(S, E, L) :-
    S rem 2 #= 0,
    S1 #= S + 1,
    every_other_number(S1, E, L).

| ?- odd_numbers(2, 8, L).

L = [3,5,7] ? ;

no
| ?- odd_numbers(2, 9, L).

L = [3,5,7,9] ? ;

no
| ?- odd_numbers(3, 8, L).

L = [3,5,7] ? ;

no
| ?-

Upvotes: 3

damianodamiano
damianodamiano

Reputation: 2662

This could be a solution, using mod/2 operator.

numbers(A,B,K) :- 
    B1 is B+1,
    numbers(A,B1,[],K).
numbers(Y,Y1,X,K) :- 
    Y = Y1,
    reverse(X,K).
numbers(A,B,X,K) :- 
    A<B, 
    C is A+1,
    C1 is mod(C,2),
    (C1 = 0 ->  
        numbers(C,B,[A|X],K)
    ; numbers(C,B,X,K)).

Upvotes: 2

Related Questions