CODEWITHSUNDEEP
recursionprologaccumulator
Ethan
Ethan

Reputation: 35

Prolog recursive accumulator

I am trying to make a knowledge base for college courses. Specifically, right now I am trying to make an accumulator that will take a course and provide a list of all classes that must be taken first, i.e. The course's prereqs, the prereqs to those prereqs, etc... Based on this chart.

Here is a sample of the predicates:

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).

And here is my attempt at an accumulator:

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.

The desired output from a query would be:

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

Instead, I get an answer of true, and a warning about Z being a singleton.

I have looked at other posts asking on similar issues, but they all had a single lane of backward traversal, whereas my solution requires multiple lanes.

Thanks in advance for any guidance.

Upvotes: 1

Views: 64

Answers (1)

Daniel Lyons
Daniel Lyons

Reputation: 22803

The problem with using forall/2 is that it does not establish bindings. Look at this contrived example:

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

If a binding were established for X or R by the forall/2, it would appear in the result; instead we just got true because it succeeded. So you need to use a construct that doesn't just run some computation but something that will produce a value. The thing you want in this case is maplist/3, which takes a goal and a list of parameters and builds a larger goal, giving you back the results. You will be able to see the effect in your console after you put in the solution below.

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

So this went and got the list of prerequisites for the two classes in the list, but gave us back a list of lists. This is where append/2 comes in handy, because it essentially flattens a list of lists:

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

Here's the solution I came up with:

prereq_chain(Class, Prereqs) :-
    findall(Prereq, prereq(Class, Prereq), TopPrereqs),
    maplist(prereq_chain, TopPrereqs, MorePrereqs),
    append([TopPrereqs|MorePrereqs], Prereqs).

Upvotes: 1

Related Questions