Prolog binary search tree test - unwanted parents' parent node comparison

Question

I'm a Prolog rookie, please keep that in mind. I try to write a predicate to determine if some given term is a binary search tree. I figured out this code:

is_btree(nil).
is_btree(node(N,L,R)) :-
   number(N),
   is_btree(L), 
   is_btree(R), 
   small(N, R),
   big(N, L).

small(N, nil).
small(N, node(M,L,R)) :-
   N < M,
   small(N, L),
   small(N, R).

big(N, nil).
big(N, node(M,L,R)) :-
   N > M,
   big(N, L),
   big(N, R).

It works quite fine until I test a graph that has a node on the right side which passes the condition "higher than parent node", but it is higher or equal to parent node of the parent node. In this case Prolog reports failure.

Here is a sample query which fails unexpectedly:

?- is_btree(node(9,node( 3,node( 2,nil,nil),
                           node(10,nil,nil)),
                   node(12,node( 8,nil,nil),
                           node(15,nil,nil)))).
false.

A very similar problem arises when some node on the left side is higher than parent node of the parent node—a situation that is shown in the following illustration:

How can I check node values only with the value of their immediate parent node, but not the values of parents' parents?

Answer 1

This answer directly follows up on this previous answer, particularly on a comment by @WillNess that suggested "[...] switch the two goals, so the traversal is stopped as soon as possible on failure [...] to have chain before the phrase [...]".

lazy_chain/2 is like chain/2, but utilizes prolog-coroutining to wait for sufficient instantiation:

:- use_module(library(clpfd)).

lazy_chain(Zs, R_2) :-
   (  var(R_2)                  -> instantiation_error(R_2)
   ;  clpfd:chain_relation(R_2) -> freeze(Zs, lazy_chain_aux(Zs,R_2))
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

lazy_chain_aux([], _).
lazy_chain_aux([Z0|Zs], R_2) :-
   freeze(Zs, lazy_chain_aux_(Zs,R_2,Z0)).

lazy_chain_aux_([], _, _).
lazy_chain_aux_([Z1|Zs], R_2, Z0) :-
   call(R_2, Z0, Z1),
   freeze(Zs, lazy_chain_aux_(Zs,R_2,Z1)).

Based on lazy_chain/2 we define is_bintreeL/2 like this:

is_bintreeL(T) :-
   lazy_chain(Zs, #<),
   phrase(in_order(T), Zs).

So... what about "early failure"?

?- T = node(2, nil, node(1, nil, node(3, nil, node(4, nil, node(5, nil, node(6, nil, node(7, nil, node(8, nil, node(9, nil, node(10, nil, node(11, nil, node(12, nil, node(13, nil, node(14, nil, node(15, nil, node(16, nil, node(17, nil, node(18, nil, node(19, nil, node(20, nil, node(21, nil, node(22, nil, node(23, nil, node(24, nil, node(25, nil, node(26, nil, node(27, nil, node(28, nil, node(29, nil, node(30, nil, node(31, nil, node(32, nil, node(33, nil, node(34, nil, node(35, nil, node(36, nil, node(37, nil, node(38, nil, node(39, nil, node(40, nil, node(41, nil, node(42, nil, node(43, nil, node(44, nil, node(45, nil, node(46, nil, node(47, nil, node(48, nil, node(49, nil, node(50, nil, node(51, nil, node(52, nil, node(53, nil, node(54, nil, node(55, nil, node(56, nil, node(57, nil, node(58, nil, node(59, nil, node(60, nil, node(61, nil, node(62, nil, node(63, nil, node(64, nil, node(65, nil, node(66, nil, node(67, nil, node(68, nil, node(69, nil, node(70, nil, node(71, nil, node(72, nil, node(73, nil, node(74, nil, node(75, nil, node(76, nil, node(77, nil, node(78, nil, node(79, nil, node(80, nil, node(81, nil, node(82, nil, node(83, nil, node(84, nil, node(85, nil, node(86, nil, node(87, nil, node(88, nil, node(89, nil, node(90, nil, node(91, nil, node(92, nil, node(93, nil, node(94, nil, node(95, nil, node(96, nil, node(97, nil, node(98, nil, node(99, nil, node(100, nil, nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))),
   time((phrase(in_order(T),Zs),eager_chain(Zs,#<))).
% 210 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4100201 Lips)
false.

?- T = node(2, nil, node(1, nil, node(3, nil, node(4, nil, node(5, nil, node(6, nil, node(7, nil, node(8, nil, node(9, nil, node(10, nil, node(11, nil, node(12, nil, node(13, nil, node(14, nil, node(15, nil, node(16, nil, node(17, nil, node(18, nil, node(19, nil, node(20, nil, node(21, nil, node(22, nil, node(23, nil, node(24, nil, node(25, nil, node(26, nil, node(27, nil, node(28, nil, node(29, nil, node(30, nil, node(31, nil, node(32, nil, node(33, nil, node(34, nil, node(35, nil, node(36, nil, node(37, nil, node(38, nil, node(39, nil, node(40, nil, node(41, nil, node(42, nil, node(43, nil, node(44, nil, node(45, nil, node(46, nil, node(47, nil, node(48, nil, node(49, nil, node(50, nil, node(51, nil, node(52, nil, node(53, nil, node(54, nil, node(55, nil, node(56, nil, node(57, nil, node(58, nil, node(59, nil, node(60, nil, node(61, nil, node(62, nil, node(63, nil, node(64, nil, node(65, nil, node(66, nil, node(67, nil, node(68, nil, node(69, nil, node(70, nil, node(71, nil, node(72, nil, node(73, nil, node(74, nil, node(75, nil, node(76, nil, node(77, nil, node(78, nil, node(79, nil, node(80, nil, node(81, nil, node(82, nil, node(83, nil, node(84, nil, node(85, nil, node(86, nil, node(87, nil, node(88, nil, node(89, nil, node(90, nil, node(91, nil, node(92, nil, node(93, nil, node(94, nil, node(95, nil, node(96, nil, node(97, nil, node(98, nil, node(99, nil, node(100, nil, nil)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))),
   time((lazy_chain(Zs,#<),phrase(in_order(T),Zs))).
% 52 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 1225664 Lips)
false.

Laziness wins—at least in above case:)

Note, however, that using lazy_chain/2 with dcg can lead to bugs that are hard to find!

For a more robust solution, see this alternative answer...

---

For the sake of completeness, here's the source code of eager_chain/2:

eager_chain(Zs, R_2) :-
   (  var(R_2)                  -> instantiation_error(R_2)
   ;  clpfd:chain_relation(R_2) -> eager_chain_aux(Zs, R_2)
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

eager_chain_aux([], _).
eager_chain_aux([Z0|Zs], R_2) :-
   eager_chain_aux_(Zs, R_2, Z0).

eager_chain_aux_([], _, _).
eager_chain_aux_([Z1|Zs], R_2, Z0) :-
   call(R_2, Z0, Z1),
   eager_chain_aux_(Zs, R_2, Z1).