1

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.

Ethan
  • 35
  • 6
  • For an accumulator you need two parameters (in & out). Start with writing a predicate `requires/2` that just takes two courses and succeeds if the 1st one requires the 2nd (or generates all the required courses). – Tomas By Aug 10 '18 at 18:12
  • Thank you Tomas - I may have gone about it the wrong way. I'll try this approach. – Ethan Aug 10 '18 at 18:17
  • Tomas: I think actually, I already have that predicate: prereq(CourseA, CourseB), which I make use of. It does work for a single layer of prereqs, but my trouble lies in the recursive calls feeding to the list. – Ethan Aug 10 '18 at 18:27
  • Yes, you need a recursive call (but no higher order stuff). – Tomas By Aug 10 '18 at 18:28
  • You have two real problems. The first is that the scope of `Z` inside the body of the `forall/2` is hidden from the outer scope where you need it. The deeper problem is that you are thinking procedurally by trying to modify Prereqs by adding stuff to it in your `forall/2` call. The final assignment of `PrereqChain = Z` is harmless but demonstrates that you're still thinking procedurally; if you instead just had `append(Prereqs, Y, PrereqChain)` and no final line, the meaning would be the same and the problem might be more obvious. – Daniel Lyons Aug 10 '18 at 19:19
  • Thank you Daniel - that does explain the singleton warning. – Ethan Aug 10 '18 at 19:32

1 Answers1

1

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).
Daniel Lyons
  • 22,421
  • 2
  • 50
  • 77