Geek Answers Handbook

Reaching the end of the list in the prologue

I was asked a question:

Define a predicate ordered by / 1, which checks the list of integers in ascending order. For example, a goal ordered([1,3,7,11])must be successful, just like a goal ordered([1,3,3,7]), while a goal ordered([1,7,3,9])must fail.

So far I have this:

ordered([]).    
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

But it does not work on every list.

I realized that the reason she fails is because she reaches a finite number in the list, and then tries to compare that number with an empty list. Obviously, this fails because you cannot compare an integer with an empty list. Even if you could, and say, return it 0for an empty list, it will still return false, since the number will be greater than 0, no less.

... ? , .

, :

ordered([]).
ordered([N]):-
    N >= 0.
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

ordered([1]), .

- ordered([N, M|Ns]) ?

+5
7

, , , .

.

ordered([]).

ordered([N, M|Ns]):-
 append([M], Ns, Tail),
 ordered(Tail),
 N =< M.

ordered([M]).

([]). , .

[] M .

? .

0

(, , ).

, , ?- ordered([1]). ( trace/0) , , .

, " " . .

+5

, . , - :

ordered([]) :-!.
ordered([_]):-!.
ordered([A,B|T]) :-
    A =< B,
    !,
    ordered([B|T]).
+2

Prolog clpfd, , clpfd:chain/2.

:- use_module(library(clpfd)).

, :

?- chain([1,3,7,11],#<).
true.

?- chain([1,3,3,7],#=<).
true.
?- chain([1,3,3,7],#<).
false.

?- chain([1,7,3,9],#<).
false.
+2

SICStus Prolog, , clpfd SICStus Prolog   chain/3, CLI-Prolog CLI > .

:- use_module(library(clpfd)).
:- assert(clpfd:full_answer).

! ordered/1 :

ordered([]).
ordered([X|Xs]) :- 
   ordered_prev(Xs,X).

ordered_prev([]     ,_ ).
ordered_prev([X1|Xs],X0) :- 
   X0 #=< X1,
   ordered_prev(Xs,X1).

SICStus Prolog 4.3.2. :

?- ordered(Xs).
  Xs = []
; Xs = [_A]
; Xs = [_A,_B],    _A#=<_B,          _A in inf..sup, _B in inf..sup
; Xs = [_A,_B,_C], _A#=<_B, _B#=<_C, _A in inf..sup, _B in inf..sup, _C in inf..sup
... % an infinity of solutions follows: omitted for the sake of brevity.

, OP:

?- ordered([1,3,7,11]).
yes                                  % succeeds deterministically
?- ordered([1,3,3,7]).
yes                                  % succeeds deterministically
?- ordered([1,7,3,9]).
no

, , .

+2

: : ordered:

  • >
  • , ordered

, , , [3]? ordered? , , : , .

- , , . , , .

+1

append/3.

edit1 to satisfy @false. To make it tail recursive, it must eliminate the rollback. This is tail-recursive and only minor variations on @Xonix:

ordered([X|[]]):-!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).

edit2 Take one more step to eliminate lists containing less than two items

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

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).
0
source

More articles:


All Articles