prolog - bst tree to list

Question

I am pracising dcg technique, but I have a problem. I am going to implement converting BST tree to list (each possible) and in reversed side - list ot bst (each possible). (List means set in real here).
However,
this grammar should be ok, but it generates very much duplicates. I know cause (nil), but I can't deal with it.

 bstToList(nil) --> [].
    bstToList(t(Root, L, R)) --> [Root], bstToList(L), bstToList(R).
    bstToList(t(Root, L, R)) --> [Root], bstToList(R), bstToList(L).
    bstToList(t(Root, L, R)) -->  bstToList(R), [Root], bstToList(L).
    bstToList(t(Root, L, R)) -->  bstToList(L), [Root], bstToList(R).
    bstToList(t(Root, L, R)) --> bstToList(L), bstToList(R), [Root].
    bstToList(t(Root, L, R)) --> bstToList(R), bstToList(L), [Root].

Could you help me ?

score 2 · Accepted Answer · edited May 23 '17 at 12:23

The problem with how you've implemented it is that you are commingling each traversal method at each traversal step. In other words, at each traversal step, your predicate will explore every traversal method.

You need to break them out at a higher level:

bst_to_list(BST, Ls) -->
    bst_to_list_pre_LR(BST, Ls, _) |
    bst_to_list_pre_RL(BST, Ls, _) |
    bst_to_list_in_LR(BST, Ls, _) |
    bst_to_list_in_RL(BST, Ls, _) |
    bst_to_list_post_LR(BST, Ls, _) |
    bst_to_list_post_RL(BST, Ls, _).

Then implement each type individually:

% Pre-order, left-to-right
bst_to_list_pre_LR(nil, Es, Es) --> [].
bst_to_list_pre_LR(t(Root, L, R), [_|Es0], Es) -->
    [Root],
    bst_to_list_pre_LR(L, Es0, Es1),
    bst_to_list_pre_LR(R, Es1, Es).

% Pre-order right-to-left
bst_to_list_pre_RL(nil, Es, Es) --> [].
bst_to_list_pre_RL(t(Root, L, R), [_|Es0], Es) -->
    [Root],
    bst_to_list_pre_RL(R, Es0, Es1),
    bst_to_list_pre_RL(L, Es1, Es).

... % Etc...

Also, read again carefully @mat's answer to your prior question, Prolog, reconstruct BST trees from inorder list, since there are useful techniques presented there for a more robust solution for each of these cases. I've incorporated that technique in the above code.

Note that you still may get duplicates since, some trees can yield the same results when traversed in different ways.

In light of the comments, it appears that a solution is sought to define a relation between a BST and a list of nodes such that the order in the BST could be arbitrary. Since the ordering could be anything, it doesn't lend itself well to a DCG. Here is a possible non-DCG solution:

bst_list_all(BST, L) :-
    tree_list_bound(BST, L, _),
    bst_list_all_(BST, L).

bst_list_all_(nil, []).
bst_list_all_(t(Root, L, R), Es) :-
    select(Root, Es, Es1),
    append(Ls, Rs, Es1),
    bst_list_all_(L, Ls),
    bst_list_all_(R, Rs).

tree_list_bound(nil, [], []).
tree_list_bound(t(_, L, R), [_|Es0], Es2) :-
    tree_list_bound(L, Es0, Es1),
    tree_list_bound(R, Es1, Es2).
tree_list_bound(t(_, L, R), [_|Es0], Es2) :-
    Es0 = [_|_],
    tree_list_bound(R, Es0, Es1),
    tree_list_bound(L, Es1, Es2).

The predicate tree_list_bound establishes a bounded framework for the solution to avoid termination issues. It "feels" like this solution could be condensed, but I haven't yet found a way to do it. However, it does seem to provide a solution to the revealed question without yielding duplicate solutions.

?- bst_list_all(t(1,nil,t(2,t(3,nil,nil),nil)), L).
L = [1, 2, 3] ;
L = [1, 3, 2] ;
L = [2, 1, 3] ;
L = [3, 1, 2] ;
L = [2, 3, 1] ;
L = [3, 2, 1] ;
false.

?- bst_list_all(BST, [1,2,3]).
BST = t(1, t(2, t(3, nil, nil), nil), nil) ;
BST = t(1, t(3, t(2, nil, nil), nil), nil) ;
BST = t(2, t(1, t(3, nil, nil), nil), nil) ;
BST = t(2, t(3, t(1, nil, nil), nil), nil) ;
BST = t(3, t(1, t(2, nil, nil), nil), nil) ;
BST = t(3, t(2, t(1, nil, nil), nil), nil) ;
BST = t(1, t(2, nil, t(3, nil, nil)), nil) ;
BST = t(1, t(3, nil, t(2, nil, nil)), nil) ;
BST = t(2, t(1, nil, t(3, nil, nil)), nil) ;
BST = t(2, t(3, nil, t(1, nil, nil)), nil) ;
BST = t(3, t(1, nil, t(2, nil, nil)), nil) ;
BST = t(3, t(2, nil, t(1, nil, nil)), nil) ;
BST = t(1, nil, t(2, t(3, nil, nil), nil)) ;
BST = t(1, nil, t(3, t(2, nil, nil), nil)) ;
BST = t(2, nil, t(1, t(3, nil, nil), nil)) ;
BST = t(2, nil, t(3, t(1, nil, nil), nil)) ;
BST = t(3, nil, t(1, t(2, nil, nil), nil)) ;
BST = t(3, nil, t(2, t(1, nil, nil), nil)) ;
BST = t(1, nil, t(2, nil, t(3, nil, nil))) ;
BST = t(1, nil, t(3, nil, t(2, nil, nil))) ;
BST = t(2, nil, t(1, nil, t(3, nil, nil))) ;
BST = t(2, nil, t(3, nil, t(1, nil, nil))) ;
BST = t(3, nil, t(1, nil, t(2, nil, nil))) ;
BST = t(3, nil, t(2, nil, t(1, nil, nil))) ;
false.

?-

`phrase(bst_to_list(t(4, t(3, t(1,nil,nil), t(5,nil,nil)), t(6,nil,nil) )), X).`. For it it returns: `X = [4, 3, 1, 5, 6] ; X = [4, 6, 3, 5, 1] ; X = [1, 3, 5, 4, 6] ; X = [1, 5, 3, 6, 4] ; X = [6, 5, 1, 3, 4]` it is too little - for example lack of `[1,3,4,5,6]`. — , May 21 '16 at 18:01
@HaskellFun I don't think `[1,3,4,5,6]` is a valid case unless you really do truly want to "mix and match" traversal methods at each iteration. In which case, yes, you will get duplicates per your original problem. — lurker, May 21 '16 at 18:06
Then, for example: `phrase(bst_to_list(X), [1,3,4,5,6]) can;t find tree that I showed in above comment. Is it possible to achieve this solution ? — , May 21 '16 at 18:10
@HaskellFun I had a typographical error in my example in the answer which I fixed. And I don't know what you implemented, but when I tried a complete solution per my answer, I was able to get a solution from your example query. — lurker, May 21 '16 at 18:20
@HaskellFun if you implement the full predicate using the pattern I showed in the answer, you should get multiple solutions to `Ls = [1,3,4,5,6], phrase(bst_to_list(X, Ls), Ls).` (Note that using @mat's answer from before prevents the predicate from having termination issues). — lurker, May 21 '16 at 18:35
`phrase(bst_to_list(t(4, t(3,nil,nil), t(6,nil,nil)), Ls), Ls). Ls = [4, 3, 6] ; Ls = [4, 6, 3] ; Ls = [3, 4, 6] ; Ls = [3, 6, 4] ; Ls = [6, 3, 4].` lack of `[6,4,3]` for example. — , May 21 '16 at 19:00
@HaskellFun when I run that query with my code I get all the results including `[6,4,3]` so you must have a mistake in following my answer. — lurker, May 21 '16 at 19:47
yes, I find small error, but look at this: `phrase(bst_to_list(t(4, t(3,t(1,nil,nil),nil), t(6,nil,nil)), Ls), Ls). Ls = [4, 3, 1, 6] ; Ls = [4, 6, 3, 1] ; Ls = [1, 3, 4, 6] ; Ls = [6, 4, 3, 1] ; Ls = [1, 3, 6, 4] ; Ls = [6, 1, 3, 4].` lack of `[1,6,4,3]` — , May 21 '16 at 20:04
@HaskellFun are you going to make me do all of your work for you? ;) `[1,6,4,3]` is not a valid traversal. It doesn't match any one of the 6 methods. It "jumps around" the tree. This gets back to my previous question: what traversal methods do you want to support? — lurker, May 21 '16 at 20:05
Yes, I understand. Nevertheless, I would like to be able find *every* list. — , May 21 '16 at 20:07
@HaskellFun if you want truly every list, then you really are just asking for a permutation of all possible visits. If I were writing code to generate that, I would simply traverse the tree once to gather the nodes, then run a permutation algorithm. Your original attempt in your question suggests you are looking for "normal" traversal methods. — lurker, May 21 '16 at 20:08
I thought about it, but how do you deal with reversed query ? Someone give you list, and you must build `every tree`. Still generating permutation ? — , May 21 '16 at 20:09
@HaskellFun yes I see what you mean. I'd have to think about that. But we're no longer talking specific traversal methods but *Every possible BST that contains the given list of nodes* regardless of order. — lurker, May 21 '16 at 20:11

prolog - bst tree to list

1 Answers1

Linked