Clever Geek Handbook

Prolog binary list output

I am working on a binary tree program in Prolog. The specific issue I am facing is a workaround. Here's what I have:

inOrder(bttree(_,L,_),T):-  inOrder(L,T).
inOrder(bttree(N,_,_),T) :- T1 = T, append(T1,N,T).
inOrder(bttree(_,_,R),T):-  inOrder(R,T).

I requested it with:

inOrder(bttree(20,
    bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)) bttree(30)), T).

so the output MUST be:

[5,10,15,20,30];
false.

But when I run it, it just returns false. I'm pretty sure the problem is with my use of append / 3, but I just can't seem to solve it. If anyone can help it would be greatly appreciated

+3


source to share


3 answers


this one is T1 = T, append(T1,N,T)

equivalent append(T,N,T)

and doomed to cycle ...

some fixes ...

inOrder(nil, []).
inOrder(bttree(N, L, R),T) :-
  inOrder(L, LT),
  inOrder(R, RT),
  append(LT, [N|RT], T).


Test:

?- inOrder(bttree(20, bttree(10, bttree(5,nil,nil), bttree(15,nil,nil)), bttree(30,nil,nil)), T).
T = [5, 10, 15, 20, 30].
0


source


I get a rather infinite loop for the request (note the missing comma in the original request):

?- inOrder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30)), T).

And I get the same infinite loop, even after adding targets to your program . The resulting program is called false

failure-slice:

inOrder (bttree (_, L, _), T): - false , inOrder (L, T) .
inOrder (bttree (N, _, _), T): - T1 = T, append (T1, N, T), false .
inOrder (bttree (_, _, R), T): -   false , inOrder (R, T) .

So this rest of the sentence triggers this cycle. In fact, any request with node bttree/3

will now be looped, even

 ?- inOrder(bttree(20, nil,nil), T).

So, we need to fix at least the rest of the visible part.

Not that the sentences are read independently, so your first sentence reads:



inOrder(bttree(_,L,_),T):- inOrder(L,T).

So the traversal of the order node will just traverse the left subtree. It doesn't seem right.

What you really want is to describe them together. The best way is not to use append/3

, but ratherdcg:

inorder(nil) --> [].
inorder(bttree(N,L,R)) -->
   inorder(L),
   [N],
   inorder(R).

Now we get:

?- phrase(inorder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30))), T).
false.

Again, a lie! But this time it bttree(30)

should be replaced:

?- phrase(inorder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30,nil,nil))), T).
T = [5,10,15,20,30].
+2


source


Just in case you don't want dcg:

inOrder( nil, [] ).
inOrder( btree( L, N, R ), T ) :- 
    inOrder( L, TL ),
    inOrder( N, TN ),
    inOrder( R, TR ),
    append( TL, TN, TLN ),
    append( TLN, TR, T ).
0


source






More articles:


All Articles