Prolog - Creating a list

Question

Need a hand here creating a list. I need to return all possible combinations of prerequisites of courses, including the prerequisites of prerequisites.

Here are some rules and facts that I need to use, (Some provided, some I've created).

prereqFor(engg233, []).
prereqFor(encm339, [engg233]).
prereqFor(cpsc217, []).
prereqFor(cpsc219, [cpsc217]).
prereqFor(cpsc231, []).
prereqFor(cpsc233, [cpsc231]).
prereqFor(math271, [X]) :-
   member(X, [math211, math213]).
prereqFor(math273, []).
prereqFor(cpsc319, [C]) :- 
   member(C, [cpsc219, cpsc233, cpsc235, encm339]).
prereqFor(cpsc331, [M, C]) :- 
   member(M, [math271, math273]), 
   member(C, [cpsc219, cpsc233, cpsc235, encm339]).
prereqFor(cpsc335, [C]) :- 
   member(C, [cpsc319, cpsc331]).

Now what I'm trying to do to accomplish this is two functions, one of which is a helper... And I can't seem to populate a list by using [H|T] or append... My current attempt:

allPrereqFor(Course, Prerequisites) :-
   prereqFor(Course, Prerequisites),
   creatingList(Course, Prerequisites, []).

creatingList(Course, Prerequisites, OnGoingList) :-
   append(Course, Prerequisites, myList).

I also tried something like:

allPrereqFor(Course, Prerequisites) :-
   prereqFor(Course, Prerequisites),
   creatingList(Prerequisites, []).

creatingList(Addition, OnGoingList) :-
   [Addition | OnGoingList].

I can't even get the most simple output before I even attempt a recursive case.

I have not listed every prereqFor function, but an example output would be:

| ?- allPrereqFor(cpsc331, X).
X = [cpsc217,cpsc219,math211,math271] ? ;
X = [cpsc231,cpsc233,math211,math271] ? ;
X = [consent235,cpsc235,math211,math271] ? ;
X = [encm339,engg233,math211,math271] ? ;

Another attempt at a solution...

allPrereqFor(Course,[],Result) :-   append([Course],[],Result).
allPrereqFor(Course, X,Result) :-   prereqFor(Course, Y),
                                    Y=[H|T],
                                    allPrereqFor(H,X,Result).

The trace:

| ?- allPrereqFor(cpsc331,X).
  1    1  Call: allPrereqFor(cpsc331,_23) ? 
  1    1  Exit: allPrereqFor(cpsc331,[]) ? 

X = [] ? ;
  1    1  Redo: allPrereqFor(cpsc331,[]) ? 
  2    2  Call: prereqFor(cpsc331,_92) ? 
  3    3  Call: member(_78,[math271,math273]) ? 
  3    3  Exit: member(math271,[math271,math273]) ? 
  4    3  Call: member(_80,[cpsc219,cpsc233,cpsc235,encm339]) ? 
  4    3  Exit: member(cpsc219,[cpsc219,cpsc233,cpsc235,encm339]) ? 
  2    2  Exit: prereqFor(cpsc331,[math271,cpsc219]) ? 
  5    2  Call: allPrereqFor(math271,_23) ? 
  5    2  Exit: allPrereqFor(math271,[]) ? 
  1    1  Exit: allPrereqFor(cpsc331,[]) ? 

X = [] ? ;
  1    1  Redo: allPrereqFor(cpsc331,[]) ? 
  5    2  Redo: allPrereqFor(math271,[]) ?

When I trace I can see that it's recursively hitting all the right courses, but it just keeps outputting:

X = [] ?;

As an assignment you should not add facts by yourself i think, can you post original facts. — Luai Ghunim, Dec 07 '17 at 02:07
A different way to explain "combinations of prerequisites" is "build of materials". If you search for "Prolog Bill of Materials" you will find [this](http://www.amzi.com/manuals/amzi/pro/ref_dcg.htm#DCGBillMaterials). While not an exact answer it will put you in the ball park. :) — Guy Coder, Dec 07 '17 at 02:16
Something else that might help you learning Prolog is to see examples of very simple exercises solved with Prolog but also solved in another programming language. See [this](http://rosettacode.org/wiki/Category:Prolog) — Guy Coder, Dec 07 '17 at 02:21
It's close, but it's the part that I already have... an analogous example would be if you could select different tires and output each combination. i.e. (spoke, chain, dunlop) (spoke, chain, goodyear) (spoke, chain, yomoto), but every part has a different combination, and so if there were 3 types of spokes, 3 types of chains, and 3 types of tires, I would need to output 27 different combinations. This is where I'm stuck. — john stamos, Dec 07 '17 at 02:24
I worked on this a little to better understand it. Are you saying that for `math271` it would not be both `math211` **and** `math213` but `math211` **or** `math213`? — Guy Coder, Dec 07 '17 at 02:52
@false are you planning to answer this. I was working on an answer but obviously yours will be the better one. :) — Guy Coder, Dec 07 '17 at 12:04
@false I just woke up on the east coast of the US. I didn't see his answer to my question until I woke up 10 minutes ago. first world problems. — Guy Coder, Dec 07 '17 at 12:08
How should the prerequisites for `cpsc331` be read? 1. math271 or math273 or cpsc219 or cpsc233 or cpsc235 or encm339 2. (math271 or math273) and (cpsc219 or cpsc233 or cpsc235 or encm339) 3. A different way. — Guy Coder, Dec 08 '17 at 11:43

Guy Coder · Answer 1 · 2017-12-07T14:31:42.683

If I understand your question correctly then:

You are looking to build a list of combinations based on and and or predicates.

For example

to take cpsc219 you would need to take
cpsc217 and cpsc219

to take math271 you would need to take
math211 and math271 or
math213 and math271

In the link the example used a build of materials for a bike and build of materials for practical questions is similar to your prerequisites.

This answer will be using DCG because you are constructing list and with Prolog when working mostly with list DCG is preferred.

For the bike example the DCG rules only showed and DCG rules and after seeing your answer to my question in the comment you also need or DCG rules but those were not given in the bike example.

So just to review: In Prolog and is done with , (,/2) and or which can be done with ; (;/2) but is more commonly done with multiple DCG rules. Note that , and ; as mentioned here are not list operators but operators working on goals.

An example of the bike and DCG rule for drivechain.

drivechain --> crank, pedal, pedal, chain.

Now the missing example of the or DCG rule implemented using multiple DCG rules

tire --> [dunlop].
tire --> [goodyear].
tire --> [yomoto].

or implemented using ;

tire -->
    [dunlop]; [goodyear]; [yomoto].

A working example of the and DCG rule:

?- drivechain(X,[]).
X = [crank, pedal, pedal, chain] ;
false.

A working example of the or DCG rule:

?- tire(X,[]).
X = [dunlop] ;
X = [goodyear] ;
X = [yomoto] ;
false.

So for your problem with math271 needing math211 or math213 the DCG rules would be:

math211 --> [math211].
math213 --> [math213].

math271 --> math211.
math271 --> math213.

?- math271(X,[]).
X = [math211] ;
X = [math213].

Since you noted that this is an assignment in the original post I will take that to mean homework so I won't give a specific answer to your question but show you something similar using the bike example.

bike --> frame, drivechain, wheel, wheel.    
wheel --> spokes, rim, hub, tire.

tire --> [dunlop].
tire --> [goodyear].
tire --> [yomoto].

drivechain --> crank, pedal, pedal, chain.

spokes --> [spokes].
crank --> [crank].
pedal --> [pedal].
chain --> [chain].
rim --> [rim].
hub --> [hub].
frame --> [frame].

?- bike(X,[]).
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear] ;
X = [frame, crank, pedal, pedal, chain, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto].

Notice that even though a tire is composed of three brands, there are 9 answers because there are two wheels each with a tire and each tire can be one of three brands thus 3 * 3 is 9.

SWI-Prolog specific:
Since some of these answers will be long and truncated with ... see this answer for help to see the entire answer without the .... In other words append ;false to the query and press w after the first answer, then press the space bar for more answers.

Since DCG is like syntactic sugar, to see the de-sugared DCG rules ( --> ) as predicates ( :- ) use listing/1, e.g.

?- listing(wheel).
wheel(A, E) :-
        spokes(A, B),
        rim(B, C),
        hub(C, D),
        tire(D, E).
true.

As I noted in the comments, I see that @false is probably going to answer this. I learn from him so I fully expect his answer to be better than mine, but I am posting my answer because if anyone sees a problem with my answer and points it out then I will learn also.

===================================

A more elaborate bike example that can make a bicycle or a tricycle.

bike --> type.
type --> bicycle.
type --> tricycle.
bicycle --> bicycle_frame, bicycle_drivechain, wheel, wheel.
tricycle --> tricycle_frame, tricycle_drive, wheel, wheel, wheel.
wheel --> spokes, rim, hub, tire.
bicycle_drivechain --> crank, pedal, pedal, chain.
tricycle_drive --> crank, pedal, pedal.
bicycle_frame --> [bicycle_frame].
tricycle_frame --> [tricycle_frame].
tire --> [dunlop].
tire --> [goodyear].
tire --> [yomoto].
spokes --> [spokes].
crank --> [crank].
pedal --> [pedal].
chain --> [chain].
rim --> [rim].
hub --> [hub].

?- bike(X,[]);false.
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear] ;
X = [bicycle_frame, crank, pedal, pedal, chain, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear, spokes, rim, hub, yomoto] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto, spokes, rim, hub, dunlop] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto, spokes, rim, hub, goodyear] ;
X = [tricycle_frame, crank, pedal, pedal, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto, spokes, rim, hub, yomoto] ;
false.

We've never seen --> but it seems fairly self explanatory... This seems to be a fairly manual approach though. I was hoping to use all the predicates that I created in Part A, (which would make sense for the assignment) as part of my recursion,i.e. following the logic... — john stamos, Dec 08 '17 at 04:04
allPrereqFor(parentCourse, X) :- use prereqFor(parentCourse,X) somehow... Creates a list of all direct prereqs... Recurse (with helper function?) across all prereqs of the parent course, again with prereqFor(1stprereq,X), prereqFor(2ndprereq,X)... Continue recursion until [] meaning it's a course with no prereqs... We are left with X=[prereq, prereqs-prereq, prereq, prereq, prereq's-prereq's-prereq, prereq]? — john stamos, Dec 08 '17 at 04:08
Thanks for the update with the output for `cpsc331` I now see that my answer is not grouping as you need. I will work on it. — Guy Coder, Dec 08 '17 at 12:01

score 0 · Answer 2 · answered Dec 07 '17 at 02:59

0

Finding the pre-requirements of pre-requirements can be done recursively. Well, you should make use of findall/3 and also flatten/2 which are defined in prolog library.

pre(X,Y):-
    preRequirement(X,Y).


preRequirement(X,[(X-List)|Y]):-
    findall(Z,prereqFor(X,Z),Res),
    flatten(Res,List),
    findPreOfPre(List,Y).


findPreOfPre([],[]).
findPreOfPre([H|T],[(H-L)|Result]):-
    findall(P,prereqFor(H,P),N),
    flatten(N,L),
    findPreOfPre(T,Result).

answered Dec 07 '17 at 02:59

Luai Ghunim

976
7
14

Not working. Only outputs direct prereqs. Though it does output 4 cpsc319's and 8 cpsc331's, which says it's recursing properly... – john stamos Dec 07 '17 at 06:35
Can you show an example what do you want? you said "Pre-requirements of pre-requirements" that's what this code does. – Luai Ghunim Dec 07 '17 at 19:07
Copied it directly to see if it would work and I only get the direct prerequisite. – john stamos Dec 08 '17 at 03:38
@johnstamos if query `pre(cpsc319,X).` then it will will return you a list of pre-requirement of `cpsc319` and also the pre-requirements for `cpsc219, cpsc233, cpsc235, encm339` which are pre-requirements for `math319` – Luai Ghunim Dec 08 '17 at 03:41
Okay I see now. Sorry. The format was throwing me off. I should be providing an example output. I have updated the question... – john stamos Dec 08 '17 at 03:55

Prolog - Creating a list

2 Answers2