Sicstus Prolog - Как построить дерево из списка

Question

У меня проблема с созданием дерева из списка.

Пример: у меня есть List = [1,2,3,4], и после запуска я хочу получить ответ, подобный этому

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

Я новичок в Sicstus.Я пытался использовать код:

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

Это работает, когда в списке только один элемент, но когда в списке более одного элемента, я получаю код ошибки:

Ошибка ресурса: недостаточно памяти

Answer 1

Как заметил @Kaarel, вырожденная форма двоичного дерева, которое вы получаете, когда узлы вставляются в последовательность, представляет собой связанный список:

Запись списка Пролога простосинтаксический сахар для нормального термина пролога: ./2, где 1-й аргумент является главой списка, а 2-й - хвостом списка.Символом пустого списка является атом «[]».Итак, внутреннее представление списка типа [1,2,3] - это структура / термин

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

Список из одного элемента, [1] как

.( 1 , '[]' )

И пустой список какatom '[]'.

Вы можете увидеть привлекательность синтаксического сахара.

См. http://cs.union.edu/~striegnk/learn-prolog-now/html/node78.html для более подробной информации.

Учитывая эту идентичность, что-то вродеэто даст вам то, что в оригинальном сообщении говорится, что вы хотите:

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

Хотя все, что вы делаете, это смена функтора.Тем не менее, ваша структура, кажется, не допускает пустого списка / дереваКак вы собираетесь представлять это?

Answer 2

Вам не нужно ничего делать, список - это дерево, например ::

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

Answer 3

Обратите внимание, что заглавные символы обычно зарезервированы для переменных (пролог ISO). Вот мое решение:

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