prologbinary-search-treedcgfailure-slice# Enumerate inorder in Prolog

I'm trying to "reverse" an inorder traversal by turning the inorder list back into BSTs.

BSTs has the predicate form `node(Value,Left,Right)`

or `leaf`

, so the empty tree is just `leaf`

, a tree with one node is `node(_,leaf,leaf)`

.

Given the predicate `enumerate_bst(Elems,Bst)`

, the goal is to match `Bst`

to all possibilities of the inorder list `Elems`

. For example (note setof/3):

```
?- setof(Bst,enumerate_bst([],Bst),Enum).
Enum = [leaf].
?- setof(Bst,enumerate_bst([1,2],Bst),Enum).
Enum = [
node(1, leaf, node(2, leaf, leaf)),
node(2, node(1, leaf, leaf), leaf)
].
?- setof(Bst,enumerate_bst([1,2,3],Bst),Enum).
Enum = [
node(1, leaf, node(2, leaf, node(3, leaf, leaf))),
node(1, leaf, node(3, node(2, leaf, leaf), leaf)),
node(2, node(1, leaf, leaf), node(3, leaf, leaf)),
node(3, node(1, leaf, node(2, leaf, leaf)), leaf),
node(3, node(2, node(1, leaf, leaf), leaf), leaf)
].
```

*What I tried to do:*

I already have a predicate that matches a given BST to it's inorder list:

```
inorder(leaf,[]).
inorder(node(X,L,R),Elems) :-
inorder(L,Elems_L),
inorder(R,Elems_R),
append(Elems_L,[X],Tmp),
append(Tmp,Elems_R,Elems).
```

I tried to use it in reverse by putting in a list instead, but this only returned one result, I'm not exactly sure why.

*What I'm currently trying to do*

I'm trying to use the native predicate append/3 in reverse, but can't fully decide how this will be done.

Any ideas as to the best way to do this? Thanks!

Solution

In reverse, your program does not terminate. Consider:

```
?- inorder(Tree, []).
Tree = leaf
; loops.
```

We would expect that it just shows this only solution and then stops.
The actual reason is the following fragment of your program - a failure-slice. No need to look any further than that. In other words, no need to understand `append/3`

at all.

?- inorder(Tree, []),false.~~inorder(leaf,[]) :-~~. inorder(node(X,L,R),Elems) :- inorder(L,Elems_L),falsefalse.~~inorder(R,Elems_R)~~,~~append(Elems_L,[X],Tmp)~~,~~append(Tmp,Elems_R,Elems)~~.

First, this fragment needs to terminate (and fail). Only then you may consider termination of the entire program. Within this fragment, the second argument (`Elems`

) is completely ignored! The first goal that would be interested in it is the very last one (`append(Tmp,Elems_R,Elems)`

).

A naive way out would be to reorder the goals, putting the two `append/3`

goals first. That works (that is, it terminates for a ground second argument), but it is quite unsatisfying, as the program is now devoted to distributing elements of a list into trees *only*.

Here is a version that works both ways as indicated by the termination condition:

`inorder(A,B)terminates_if b(A);b(B).`

which states that `inorder/2`

terminates if the first or the second argument is ground.

```
inorder(Tree, Xs) :-
phrase(inorder(Tree, Xs,[]), Xs).
inorder(leaf, Vs,Vs) -->
[].
inorder(node(X,L,R), [_|Vs0],Vs) -->
inorder(L, Vs0,Vs1),
[X],
inorder(R, Vs1,Vs).
```

- Turbo Prolog: Create a palindrome by adding the smallest number of characters to the list
- Prolog order of clause body gives different results when using negation
- Problem With a Predicate to Check if X Occurs Exactly Four Times in a List
- Most General Unifier (Prolog)
- In prolog, functors vs predicates, and goals
- Solving N-queens with Constraint Handling Rules
- 'if' in prolog?
- Are there any Prolog compilers that can optimize by targeting specific queries?
- gprolog: Getting a stacktrace after an exception
- Efficient solution for the same-fringe problem for binary trees
- Understanding prolog \+ and the engine's solution space search
- Prolog, X element before element Y on list
- What is the difference between once and cut in prolog?
- Getting the seed set by the ECLiPSe on loading
- Get simple Prolog example to work
- How to do recursion in a L-system inspired rewrite System, without DCG
- Maximum number of atoms in SICStus Prolog 4
- How to create a list dynamically in Prolog?
- Prolog Syntax for Dependent Conditions
- Guard clauses in prolog?
- phrase_from_stream/2 nontermination (Stream from http_open/3)
- SWI-Prolog: [FATAL ERROR: Could not find system resources]
- DCG LaTeX printer for FOL prover
- Prolog: a person is a sibling of himself?
- When can I safely avoid storing temporary calculations in Prolog?
- Prolog - Solution of a riddle
- Is the structure of my Prolog expression isomorphic to the structure of the Liar Paradox?
- Syntax error: Operator expected in Prolog
- Assertion Failure in SWI-Prolog When Using pyswip to Consult a Prolog File
- Retract by partial match?