О слиянии списков в Прологе

Question

Я сейчас изучаю пролог, но я встретил несколько интересных вопросов.

Цель состоит в том, чтобы распечатать список семейных отношений,

факты:

parent(john, paul).
parent(john, mary).
parent(paul, henry).
parent(paul, june).
parent(henry, helen).
parent(mary, adam).

Цель состоит в том, чтобы напечатать список следующим образом,

L =
[john,
  [paul,
    [henry,
      [helen]
    ],
    [june]
  ],
  [mary,
    [adam]
  ]
]

Вот мой код и то, что я получаю сейчас,

descendantTree(X, [X|[T1]]) :- parent(X, Tmp),                        
                            descendantTree(Tmp, T1).
descendantTree(X, [X]) :- not(parent(X, Tmp)).

[debug]  ?- descendantTree(john, L).
         L = [john, [paul, [henry, [helen]]]] ;
         L = [john, [paul, [june]]] ;
         L = [john, [mary, [adam]]] ;
         false.

Я потерял в объединении этих результатов, если я смогу получить какую-либо помощь, он будет очень признателен.Спасибо!

Answer 1

Я думаю, что вы находитесь на правильном пути, ясно, что первый элемент списка для descendantTree/2 из X - это X, и за ним может (необязательно) следовать списокchildren.

Мы можем сгенерировать эти дочерние списки с помощью вызова findall/3, где мы делаем рекурсивный вызов нашего собственного предиката, например:

descendantTree(X, [X | Ds]) :-
    findall(D, (parent(X, C), descendantTree(C, D)), Ds).

Учитывая, что "childs" не существуетC, тогда Ds будет пустым, поэтому мы сгенерируем одноэлементный список с бездетным родителем в качестве элемента.

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

Например:

?- descendantTree(john, L).
L = [john, [paul, [henry, [helen]], [june]], [mary, [adam]]].

, к сожалению, мы не можем легко сгенерироватьдерево в обратном порядке:

?- descendantTree(P, L).
L = [P, [paul, [henry, [helen]], [june]], [mary, [adam]], [henry, [helen]], [june], [helen], [adam]].

здесь свободная переменная P будет просто соответствовать чему-либо и, таким образом, будет соответствовать всем parent/2 фактам.Мы можем предотвратить это.Я оставляю это как упражнение.