Попытка написать предикат высоты дерева - мне нужны натуральные числа в стиле Пеано?

В качестве основного упражнения на Прологе я поставил перед собой задачу написать предикат высоты двоичного дерева, который будет работать вперед и назад, то есть, помимо определения высоты известного двоичного дерева, он должен быть в состоянии найти все двоичные файлы. деревья (в том числе несбалансированные) известной высоты. Это лучшее решение, которое я придумала до сих пор...

tree_eq1([],s).  % Previously had a cut here - removed (see comments for reason)
tree_eq1([_|T],n(L,R)) :- tree_eq1(T,L), tree_eq1(T,R).
tree_eq1([_|T],n(L,R)) :- tree_eq1(T,L), tree_lt1(T,R).
tree_eq1([_|T],n(L,R)) :- tree_lt1(T,L), tree_eq1(T,R).

tree_lt1([_|_],s).
tree_lt1([_,X|T],n(L,R)) :- XX=[X|T], tree_lt1(XX,L), tree_lt1(XX,R).

Первым аргументом является высота, выраженная в виде списка - элементы не имеют значения, длина списка выражает высоту дерева. Поэтому я в основном злоупотребляю списками как натуральными числами в стиле Пеано. Это удобно по следующим причинам:

  1. Не беспокойтесь о отрицательных числах.
  2. Я могу проверить> или>=, не зная точного числа - например, сопоставляя два элемента в начале списка, я гарантирую, что длина списка>=2, не заботясь о длине хвоста.

Похоже, что ни одно из этих свойств не применимо к числам Пролога, и я пока не могу придумать, как адаптировать тот же базовый подход для использования реальных чисел вместо этих списков.

Я видел несколько примеров в Прологе с использованием чисел в стиле Пеано, поэтому мой вопрос - это нормальная практика? Или есть какой-то способ избежать проблемы, которую я еще не заметил?

Кроме того, есть ли способ преобразования в / из представления в стиле Peano, который не нарушит двунаправленность? Следующее не работает по довольно очевидным причинам...

length(L,N), tree_eq1(L,X).
  % infinite set of lists to explore if N is unknown

tree_eq1(L,X), length(L,N)
  % infinite set of trees to explore if X is unknown

Лучшее, что я могу придумать, - это создание экземпляра "это переменная" для выбора между реализациями, что мне кажется обманом.

Кстати, у меня есть некоторые идеи для других методов, для которых я не хочу спойлеров - в частности, вид динамического программирования. Я действительно сосредоточен на полном понимании уроков этой конкретной попытки.

Источник

1 ответ

Решение

Во-первых: +1 для использования длин списков для подсчета, что иногда действительно очень удобно и хорошая альтернатива для записи преемника.

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

Например, с SICStus Prolog или SWI:

:- use_module(library(clpfd)).

tree_height(s, 0).
tree_height(n(Left,Right), Height) :-
        Height #>= 0,
        Height #= max(HLeft,HRight) + 1,
        tree_height(Left, HLeft),
        tree_height(Right, HRight).

Пример запроса:

?- tree_height(Tree, 2).
Tree = n(s, n(s, s)) ;
Tree = n(n(s, s), s) ;
Tree = n(n(s, s), n(s, s)) ;
false.

В-третьих, обратите внимание, что самый общий запрос, ?- tree_eq1(X, Y)., не работает удовлетворительно с вашей версией. С приведенным выше фрагментом, по крайней мере, он дает бесконечное количество решений (как и должно быть):

?- tree_height(T, H).
T = s,
H = 0 ;
T = n(s, s),
H = 1 ;
T = n(s, n(s, s)),
H = 2 .

Я оставляю их справедливое перечисление в качестве упражнения.

Источник
Другие вопросы по тегам