Пролог: считать только прямые дочерние узлы родителя, используя чистую рекурсию

Возможно ли в Prolog подсчитать количество прямых дочерних узлов родителя, используя рекурсию без retract/aggregate и т. д.?

Например, скажем, у нас есть следующее:

parent(p1, child_node1).
parent(p1, child_node2).
parent(p1, child_node3).
parent(p1, child_node4).

parent(child_node1, another_node1).
parent(child_node1, another_node2).
parent(child_node2, another_node3).
parent(child_node2, another_node4).
parent(child_node3, another_node5).
parent(child_node3, another_node6).
parent(child_node4, another_node7).
parent(child_node4, another_node8).

Как с помощью рекурсии подсчитать, что p1 имеет 4 прямых дочерних узла?


parent children tree prolog
person curiousMinded    schedule 22.09.2019    source источник
comment
Почему не с findall/3? Использование рекурсии сделает программу неэффективной, так как она по сути каждый раз будет делать очередной обход дерева вычислений.   -  person Willem Van Onsem    schedule 22.09.2019
comment
Меня просто интересует, можно ли (и как) этого добиться, используя, так сказать, только чистую рекурсию. Конечно, есть более эффективные способы добиться этого.   -  person curiousMinded    schedule 22.09.2019
comment
Вы придумали эскиз (или попытку) решить это самостоятельно?   -  person Willem Van Onsem    schedule 22.09.2019
comment
Я могу добиться этого, используя один из retract / aggregate_all или findall/3, но без них у меня не было большого успеха. Мои текущие мысли состоят в том, чтобы создать список и заполнить его детьми, а затем подсчитать его длину. Однако, будучи новичком в Прологе, я чувствую, что что-то упускаю, не зная, как мне быть уверенным, что я не зацикливаюсь вечно на одних и тех же дочерних элементах.   -  person curiousMinded    schedule 22.09.2019

Ответы (1)


arrow_upward
0
arrow_downward

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

count_children(Parent, N) :-
    count_children(Parent, [], 0, N).

count_children(Parent, L, N0, N) :-
    (parent(Parent, C), \+member(C, L))
    -> (N1 is N0+1, count_children(Parent, [C|L], N1, N))
    ; N = N0.

Например:

?- count_children(p1, N).
N = 4.

?- count_children(child_node1, N).
N = 2.

?- count_children(child_node2, N).
N = 2.

?- count_children(child_node3, N).
N = 2.

?- count_children(child_node4, N).
N = 2.

?- count_children(another_node1, N).
N = 0.

Однако, если родитель не унифицирован, он объединится с первым родителем и остановится после получения первого результата:

?- count_children(P, N).
P = p1,
N = 4.

Я оставляю это в качестве упражнения, чтобы позволить этому объединиться со всеми возможными родителями.

person Willem Van Onsem    schedule 22.09.2019
comment
Большое спасибо за это объяснение, оно прояснило для меня вещь. - person curiousMinded; 22.09.2019