0

I am going to implement getting all leaves from tree to list and vice versa - for list of leaves construct tree - I know that such trees is infitity. 

leaves(nil) --> 
    [].

leaves(t(X, nil, nil)) --> 
    [X].
leaves(t(_, t(Y, L, R), nil)) -->
    leaves(t(Y, L, R)).

leaves(t(_, t(X, LL, LR), t(Y, RL, RR))) -->
    leaves(t(X, LL, LR)),
    leaves(t(Y, RL, RR)).

Is seems to be even workin, for example

phrase( leaves(  t(6, t(3, 
            t(1, nil, nil), 
            t(5, nil, nil)
        ),           
        t(4, 
            t(2, nil, nil), 
            t(8, 
                t(7, nil, nil), 
                t(9, nil, nil)
            )
        )
    )
    ), X).
X = [1, 5, 2, 7, 9] ;
false.

One result, as expected. However, problem is in vice versa - it is looping - of course it is obvious that there are infitely such tree - but I dosen't give any result.

phrase(leaves(X), [1, 5, 2, 7, 9]) is looping, but for
phrase(leaves(X), [1]) it seems to be working in expected way: 

X = t(1, nil, nil) ;
X = t(_G8388509, t(1, nil, nil), nil) ;
X = t(_G8388509, t(_G8388513, t(1, nil, nil), nil), nil)

Is it possible to implement it such that it will be working in the same way for one-element list ?

Edit

After reexamining your prior answers, I come to following conclusions: 

leaves(nil, Ls, Ls) --> [].

leaves(t(X, nil, nil), Ls, Ls) -->[X].

leaves(t(_, t(Y, L, R), nil), [_|Ls0], Ls) -->
    leaves(t(Y, L, R), Ls0, Ls).

leaves(t(_, nil, t(Y, L, R)), [_|Ls0], Ls) -->
    leaves(t(Y, L, R), Ls0, Ls).

leaves(t(_, t(X, LL, LR), t(Y, RL, RR)), [_|Ls0], Ls) -->
    leaves(t(X, LL, LR), Ls0, Ls1),
    leaves(t(Y, RL, RR), Ls1, Ls).

phrase(leaves(X, [1,2], _), [1,2]).
X = t(_G1522, t(_G1526, t(1, nil, nil), t(2, nil, nil)), nil) ;
X = t(_G1522, nil, t(_G1526, t(1, nil, nil), t(2, nil, nil))) ;
X = t(_G1522, t(1, nil, nil), t(2, nil, nil)) ;
X = t(_G1522, t(1, nil, nil), t(_G1530, t(2, nil, nil), nil)) ;
X = t(_G1522, t(1, nil, nil), t(_G1530, nil, t(2, nil, nil))) ;
X = t(_G1522, t(_G1526, t(1, nil, nil), nil), t(2, nil, nil)) ;
X = t(_G1522, t(_G1526, nil, t(1, nil, nil)), t(2, nil, nil)) ;
false.

I expected infite result, but I got finite result. However, is it incorrect ?

  • 4
    Maybe you should check out the answers of your older questions? This is similar to what you already asked! – mat May 22 '16 at 10:02
  • 4
    As an aside, you seem to be missing a rule: `leaves(t(_, nil, t(Y, L, R))) --> leaves(t(Y, L, R)).` – lurker May 22 '16 at 10:17
  • 3
    The technique for avoiding the termination issue you've encountered was described in a [prior answer](http://stackoverflow.com/questions/37345995/prolog-reconstruct-bst-trees-from-inorder-list#answer-37346279) by @mat, and then reiterated by [an answer I provided later](http://stackoverflow.com/questions/37363525/prolog-bst-tree-to-list#37363779). You should study those answers. – lurker May 22 '16 at 11:30
  • Both `leaves(nil, Ls, Ls) --> [].` and `leaves(t(X, nil, nil), Ls, Ls) -->[X].` do nothing with `Ls`. That don't look right to me... – repeat May 22 '16 at 11:47
  • 1
    Your results are finite because your rules require that a leaf node consist only of elements from your list, and terminates after using each of them once. Which part of that do you want to relax? Use elements from your input more than once, or allow leaves not consisting of one of those elements? – lurker May 22 '16 at 15:20
  • My aim is to create all trees with leaves from list. Is it clear ? –  May 22 '16 at 19:32
  • 1
    Sorry it's not clear. See the questions in my comment. Do you want to use the elements in the list only once? Or can you use each element multiple times as leaves? If multiples, then DCG operating on the list is probably not the right approach since the DCG traverses the list once and is done. – lurker May 23 '16 at 02:29
  • **1.** For given list: it should build each tree, where all elements from list are leaves. Leaves should be as many as length of list (no dupliactes of leaves). **2.** For given tree - it should return exactly one list - leaves from left to right. Then, These operations are mutually inverse. What do you think about it now ? –  May 23 '16 at 09:24
  • 1
    From that description I don't know how you would expect an infinite number of trees for a given list since the list is finite, you expect every leaf to be an element from the list, and you don't wish to duplicate any list elements in the tree. – lurker May 23 '16 at 10:58
  • You always may add new node as root (not leaf). Then you have infinitely many possibilities. For example, let our list will be `[1]`. Then we may build tree: `1-X-X-X-X-X-X-...` (path, where `1` is only leaf). –  May 23 '16 at 21:38
  • These "leaves" `t(E,nil,nil)` of yours don't make sense to me. Why not store data in inner nodes, too? – repeat May 24 '16 at 11:45
  • data are store in inner nodes too, but leaf for me is: `t(E, nil, nil)`. It is possible, inner node for example `t(E, t(E2, nil, t(..)), t(..))` –  May 24 '16 at 15:39

0 Answers0