Рекурсивный аккумулятор Prolog

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

Вот пример предикатов:

prereq(cst250, cst126).
prereq(cst223, cst126).
prereq(cst126, cst116).
prereq(cst105, cst102).
prereq(cst250, cst130).
prereq(cst131, cst130).
prereq(cst130, cst162).
prereq(anth452, wri122).
prereq(hist452, wri122).

А вот моя попытка аккумулятора:

prereq_chain(Course, PrereqChain):-
    %Get the list of prereqs for Course
    findall(Prereq, prereq(Course, Prereq), Prereqs),

    %Recursive call to all prereqs in X
    forall(member(X, Prereqs),
           (prereq_chain(X, Y),    
            %Combine current layer prereqs with deeper
            append(Prereqs, Y, Z))),

    %Return PrereqChain
    PrereqChain = Z.

Желаемый результат запроса будет следующим:

?- prereq_chain(cst250, PrereqList).
PrereqList = [cst116, cst126, cst162, cst130]

Вместо этого я получаю ответ true и предупреждение о том, что Z является синглтоном.

Я просмотрел другие сообщения, в которых задавались похожие вопросы, но все они имели одну полосу обратного обход, тогда как мое решение требует нескольких дорожек.

Заранее спасибо за любое руководство.


recursion accumulator prolog
person Ethan    schedule 10.08.2018    source источник
comment
Для аккумулятора вам нужны два параметра (вход и выход). Начните с написания предиката requires/2, который просто принимает два курса и завершается успешно, если 1-й требует второго (или генерирует все требуемые курсы).   -  person Tomas By    schedule 10.08.2018
comment
Спасибо, Томас, возможно, я ошибся. Я попробую этот подход.   -  person Ethan    schedule 10.08.2018
comment
Томас: Думаю, у меня уже есть этот предикат: prereq(CourseA, CourseB), который я использую. Это работает для одного слоя предварительных требований, но моя проблема заключается в рекурсивных вызовах, поступающих в список.   -  person Ethan    schedule 10.08.2018
comment
Да, вам нужен рекурсивный вызов (но не более высокий порядок).   -  person Tomas By    schedule 10.08.2018
comment
У тебя две настоящие проблемы. Во-первых, область Z внутри тела forall/2 скрыта от внешней области, где она вам нужна. Более глубокая проблема заключается в том, что вы мыслите процедурно, пытаясь модифицировать Prereqs, добавляя к нему что-то в своем вызове forall/2. Окончательное задание PrereqChain = Z безвредно, но демонстрирует, что вы все еще мыслите процедурно; если бы вместо этого у вас было просто append(Prereqs, Y, PrereqChain) и не было последней строки, значение было бы таким же, и проблема могла бы быть более очевидной.   -  person Daniel Lyons    schedule 10.08.2018
comment
Спасибо, Дэниел, это объясняет одноэлементное предупреждение.   -  person Ethan    schedule 10.08.2018

Ответы (1)


arrow_upward
1
arrow_downward

Проблема с использованием forall/2 заключается в том, что он не устанавливает привязки. Посмотрите на этот надуманный пример:

?- forall(member(X, [1,2,3]), append(['hi'], X, R)).
true.

Если привязка была установлена ​​для X или R с помощью forall/2, она появится в результате; вместо этого мы просто получили true, потому что это удалось. Поэтому вам нужно использовать конструкцию, которая не просто выполняет какие-то вычисления, а что-то, что будет производить значение. В этом случае вам нужен maplist/3, который берет цель и список параметров и создает более крупную цель, возвращая вам результаты. Вы сможете увидеть эффект в своей консоли после того, как введете решение ниже.

?- maplist(prereq_chain, [cst126, cst130], X).
X = [[cst116], [cst162]].

Итак, это пошло и получило список предварительных условий для двух классов в списке, но вернуло нам список списков. Здесь пригодится append/2, потому что он существенно сглаживает список списков:

?- append([[cst116], [cst162]], X).
X = [cst116, cst162].

Вот решение, которое я придумал:

prereq_chain(Class, Prereqs) :-
    findall(Prereq, prereq(Class, Prereq), TopPrereqs),
    maplist(prereq_chain, TopPrereqs, MorePrereqs),
    append([TopPrereqs|MorePrereqs], Prereqs).
person Daniel Lyons    schedule 10.08.2018
comment
Фантастический. Большое спасибо за объяснение! - person Ethan; 10.08.2018
comment
@ Итан, нет проблем :) - person Daniel Lyons; 10.08.2018
comment
@ Итан, можешь нажать на галочку, чтобы принять ответ? - person Daniel Lyons; 10.08.2018