CODEWITHSUNDEEP
treeprolog
Ferry
Ferry

Reputation: 583

Sicstus Prolog - How to build a tree from a list

Got a problem about how to build a tree from a list.

Example: I've got List = [1,2,3,4] and after running I want to get an answer like this

T = Tree(1, Tree(2, Tree(3, 4)).

I'm new to Sicstus. I've tried using code:

build_tree([X], X).
build_tree([H|S], T) :- build_tree([S] , Tree(H, T)).

It works when there's only one element in the list, but when there're more than 1 element in the list, I get error code:

Resource error: insufficient memory

Upvotes: 0

Views: 3876

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74257

As @Kaarel noted, the degenerate form of a binary tree that you get when the nodes are inserted in sequence is a linked list:

degenerate tree

Prolog's list notation is simply syntactic sugar for a normal prolog term: ./2, where the 1st argument is the head of the list and the 2nd the tail of the list. The sigil for the empty list is the atom '[]'. So, the internal representation of a list like [1,2,3] is the structure/term

.( 1 , .( 2 , .( 3 , '[]' )

A one element list, [1] as

.( 1 , '[]' )

And the empty list as the atom '[]'.

You can see the attraction of the syntactic sugar.

See http://cs.union.edu/~striegnk/learn-prolog-now/html/node78.html for more details.

Given that identity, something like this will give you what your original post says you want:

list2tree( [X,Y] , tree(X,Y) )
  .
list2tree( [X|Xs] , tree( X , Ts ) :-
  list2tree( Xs , Ts )
  .

Though all you're doing is changing the functor. However, your structure doesn't seem to allow for the empty list/tree. How do you intend to represent that?

Upvotes: 2

CapelliC
CapelliC

Reputation: 60014

Please note that uppercase symbols are usually reserved for variables (ISO prolog). Here my solution:

build_tree([X,Y],'Tree'(X,Y)) :- !.
build_tree([X|Y],'Tree'(X,Z)) :- build_tree(Y, Z).

Upvotes: 1

Kaarel
Kaarel

Reputation: 10672

You don't need to do anything, a list is a tree, e.g.:

?- write_canonical([1, 2, 3, 4]).
'.'(1,'.'(2,'.'(3,'.'(4,[]))))
true.

Upvotes: 1

Related Questions