CODEWITHSUNDEEP
prolog
Super Learner
Super Learner

Reputation: 151

dealing with list within list in Prolog

I have the following list : 

[[[...],member,[...]],Header,[[...],member,[...]]].

which represents a binary search tree. This is my idea to build a Binary tree in Prolog, but the question is: how to access each list, and how to distinguish between them. And the most important question is: how to make a Variable 'point' (I use the concepts of C language to explain my idea) to the header of the tree, which is represented by Header.

Upvotes: 0

Views: 231

Answers (3)

user1812457
user1812457

Reputation:

Since you seem to be a beginner to Prolog, an advice (rather than an answer):

It is not necessary to represent a tree as a recursively nested list. Instead, use a recursively nested term of arity 3, for example,

  • bst(Element, Left, Right) for the tree term
  • empty for the empty tree term

(bst here stands for binary search tree)

So a balanced tree representing [1,2,3,4,5,6,7] would be:

bst(4,
    bst(2,
        bst(1,
            empty,
            empty
        ),
        bst(3,
            empty,
            empty
        )
    ),
    bst(6,
        bst(5,
            empty,
            empty
        ),
        bst(7,
            empty,
            empty
        )
    )
)

You can look into the SWI-Prolog library library(assoc). It implements self-balancing binary trees using AVL, but you can read the code anyway: it is very clear and you don't need to go into the self-balancing if you don't want to. There is also a red-black tree implementation somewhere in the source tree of SWI-Prolog, it is available through the web page as well.

Apart from that, your question is very unclear and it is difficult to understand what is the exact problem you are facing, since you are not showing any code.

EDIT:

This is a non-deterministic predicate that checks if a value is in the tree, or enumerates values in increasing order:

bst_val(bst(_, Left, _), Val) :-
    bst_val(Left, Val).
bst_val(bst(Val, _, _), Val).
bst_val(bst(_, _, Right), Val) :-
    bst_val(Right, Val).

Upvotes: 2

lurker
lurker

Reputation: 58224

Distinguishing structure in Prolog is a matter of pattern matching. If we consider your binary tree structure:

[[[...],member,[...]],Header,[[...],member,[...]]]

As @ScottHunter pointed out, it has the form:

BinTree = [Left, Head, Right]

Where Left and Right are a binary tree structure defined recursively again as [Left, Head, Right], Head represents a node value. I'm thinking this is what you intended...

Suppose you want to traverse the binary tree (cf. Tree Traversal) . You could use something like this to print all the nodes in left-to-right order:

inorder([L, H, R]) :-
    inorder(L),     % L is assumed to be of the form [L,H,R]
    write(H), nl,
    inorder(R).     % R is assumed to be of the form [L,H,R]
inorder([]).

Pre-order and post order simply follow the structure:

preorder([L, H, R]) :-
    write(H), nl,
    preorder(L),
    preorder(R).

postorder([L, H, R]) :-
    postorder(L),
    postorder(R),
    write(H), nl.

It's very simple and just follows the pattern. The knowledge of the structure of your tree is implicit in the code. Each branch is assumed to be of the form [L, H, R], and an empty branch is []. So a tree might look like: [ [[], a, [[[],d,[]], e, []]], b, [[], c, []] ]. This assumes that a node is null if it is the empty list, []. For this case you'd get:

| ?- inorder( [ [[], a, [[[],d,[]], e, []]], b, [[], c, []] ]).
a
d
e
b
c

Note that no assumption in the predicates has been made about the structure of Head. It could, itself, be a list or any other kind of Prolog term. The only structural assumption is that a binary tree is a list of 3 items: a left subtree, a head, and a right subtree. A subtree is assumed to recursively be a binary tree. An empty tree is assumed to be an empty list [].

To make a variable "point" to something, you do it through unification. For example:

BinTree = [ [[], a, [[[],d,[]], e, []]], b, [[], c, []] ]

Now BinTree is instantiated as the tree, and you can query inorder(BinTree) and get the results shown above. It can also be done in a predicate via the parameters:

unify(A, A).

If I query unify(BinTree, [ [[], a, [[[],d,[]], e, []]], b, [[], c, []] ])., then BinTree will now be instantiated with [ [[], a, [[[],d,[]], e, []]], b, [[], c, []] ].

Note that you probably want to avoid trying to think about Prolog using concepts and terms from procedural languages. It will lead you down the dark path of writing Prolog programs procedurally instead of declaratively, as it is intended to be used. And problems that should be easy to solve in Prolog will become difficult.

Upvotes: 3

Scott Hunter
Scott Hunter

Reputation: 49803

It look like each node in your tree is of the form:

[left-subtree, header, right-subtree]

If that is so, then if you have a tree T, and unify it with [L,H,R], L will be the left subtree, H will be the header, and R will be the right subtree.

Upvotes: 1

Related Questions