Получение списка детей для узла в Прологе - PullRequest
Новая
       6

Получение списка детей для узла в Прологе

0 голосов
/ 14 ноября 2018

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

Мой код: 

root(a).
node(a, [b, c]).
node(b, []).
node(c, [d, e, f]).
node(d, []).
node(e, []).
node(f, []).

children(node(_, Kids), Kids).

node_matches(_,_).
node_matches(Criteria, [Head|Tail]) :- node_matches(Criteria, Head), node_matches(Criteria, Tail).

search_node(Criteria, [Node]) :- node_matches(Criteria, Node), search_node(Criteria, children(Node)).

В настоящее время я получаю сообщение об ошибке Неопределенная процедура: children / 1, что имеет смысл, потому что я не реализовал функцию с 1 аргументом. Как я могу реализовать такую ​​функцию?

1 Ответ

0 голосов
/ 15 ноября 2018

Поскольку вас интересует список, почему бы не рассмотреть вопрос об использовании DCG для выполнения этой задачи?В конце концов, DCG описывают списки и дают легко читаемый код.Удобно, что заданный вами узел фактов / 2 предоставляет прямых преемников узла в списке, поэтому целесообразно использовать список узлов, которые необходимо посетить, в качестве единственного аргумента DCG.Сам DCG может быть назван в честь того, что он описывает, например children // 1.Вы можете определить предикат вызова, давайте также дадим ему хорошее описательное имя, скажем, node_children / 2, которое использует фразу / 2 для вызова DCG: 

node_children(N,C) :-
   node(N,Succs),             % Succs are the direct successors of node N
   phrase(children(Succs),C). % based on them the DCG children//1 describes the list C

Дети DGC // 1 должны описатьсписок, который состоит из всех узлов в его аргумент-листе и их соответствующих потомках, то есть их соответствующих преемников, преемников их преемников и т. д. (эта формулировка уже несет запах рекурсии :-).Таким образом, дети // 1 могут выглядеть примерно так: 

children([]) -->       % if there are no nodes
   [].                 % there are no children
children([N|Ns]) -->   % N, the first node in the list...
   {node(N,Succs)},    % ...has the direct successors Succs...
   [N],                % ...and is in the list of children...
   children(Succs),    % ...as well as its successors and their children...
   children(Ns).       % ...as well as the other nodes in the list

В первой цели рекурсивного правила детей // 1, {node(N,Succs)} вы можете наблюдать, как предикаты могут вызываться в DCG,а именно заключенный в фигурные скобки.Теперь давайте посмотрим на node_children / 2 в действии: 

   ?- node_children(a,C).
C = [b,c,d,e,f]
   ?- node_children(b,C).
C = []
   ?- node_children(c,C).
C = [d,e,f]

Вы также можете задать более общие запросы, такие как Какие есть узлы и соответствующие дочерние элементы? : 

   ?- node_children(N,C).
C = [b,c,d,e,f],
N = a ? ;
C = [],
N = b ? ;
C = [d,e,f],
N = c ? ;
C = [],
N = d ? ;
C = [],
N = e ? ;
C = [],
N = f

Или Какие узлы имеют трех дочерних элементов? : 

   ?- C=[_,_,_], node_children(N,C).
C = [d,e,f],
N = c ? ;
no

Два заключительных замечания: Вы можете увидеть, как дочерние элементы DCG // 1 переводятся в предикат, выполнив запрос ?- listing(children)..Чтобы узнать больше о DCG, я могу искренне рекомендовать этот учебник DCG .

...