CODEWITHSUNDEEP
prolog
IvanNickSim
IvanNickSim

Reputation: 154

Generate list and check if the values are increasing

Currently, I'm generating a list, in which each element has a value equal to the square of the preceding element plus the value of Z. After generating the list using generate_list, I want to check if it's an ordered list or not. I've implemented ordered and then in the console, I'm trying to do something like ordered(generate_list(A, B, Z,[])., which is returning always false, even when I'm sure that it must be true. I know that this approach is not good in Prolog but I don't know how to do it...

gen(0,0,_).
gen(N,F,Z) :- X is N-1,gen(X,A,Z),F is (A*A)+Z.

generate_list(A,B,Z,[]):- A>B.
generate_list(A,B,Z,[H|T]):-
    A =< B,
    gen(A,H,Z),
    AA is A + 1,
    generate_list(AA,B,Z,T).

ordered([]).
ordered([_]).
ordered([X,Y|Z]):-X=<Y,ordered([Y|Z]).

Upvotes: 2

Views: 172

Answers (3)

damianodamiano
damianodamiano

Reputation: 2662

To extend the previous answers, in particular the one from Willem Van Onsem, you can write something like:

my_ord(P,L):- 
    call(P,L),
    ordered(L).

And then you can query ?- my_ord(generate_list(5, 1),L). To remove choice points, you can use once/1 on both call/2 and ordered/1 or write another predicate like my_ord_(P,L):- once(my_ord(P,L)) or place the cut !. Considering Willem Van Onsem answer, you need to add a cut after generate_list(0, _, _, []). In your ordered/1 you need a cut after ordered([]) and ordered([_]).

Upvotes: 1

User9213
User9213

Reputation: 1316

Your ordered/1 probably works as it is. But it leaves behind a choice point! You could use once( sorted(L) ).

"Ordered" is somewhat similar to "sorted", isn't it?

If you can have duplicates in the list, use msort:

sorted(L) :- msort(L, L).

If you do not allow duplicates, use sort:

sorted_uniq(L) :- sort(L, L).

Neither leaves behind choice points.

This leaves you with the choice point left by the solution in the other answer. You can make a list and then fill it up.

generate_list(N, Z, L) :-
    length(L, N),
    generate_list_1(L, Z, 0).

generate_list_1([], _, _).
generate_list_1([X|Xs], Z, X) :-
    X1 is X^2 + Z,
    X1 >= X, % Checks for order!
    generate_list_1(Xs, Z, X1).

This implementation only gives you increasing lists and does not leave behind unnecessary choice points.

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477854

I do not really see why you specify a function gen/3 here. You can use an accumulator, and thus each time update the accumulator, like:

generate_list(N, Z, L) :-
    generate_list(N, Z, 0, L).

generate_list(0, _, _, []).
generate_list(N, Z, A, [A|T]) :-
    N > 0,
    B is A*A + Z,
    N1 is N-1,
    generate_list(N1, Z, B, T).

For example for Z is 1, we get:

?- generate_list(5, 1, L).
L = [0, 1, 2, 5, 26] ;
false.

With the ordered/1 predicate in your question, we see that this list is indeed ordered:

?- generate_list(5, 1, L), ordered(L).
L = [0, 1, 2, 5, 26] ;
false.

Whereas for Z = -1, it is not:

?- generate_list(5, -1, L).
L = [0, -1, 0, -1, 0] ;
false.

?- generate_list(5, -1, L), ordered(L).
false.

Upvotes: 3

Related Questions