How to scroll through a list in Prolog to find a specific item

Question

I am a beginner in Prolog and I have doubts about how to go through a list.

I have a predicate historico(ra,[i1,i2,i3,...,in]) where ra is the Academic Record of a student and each i is an item, with the shape item(CM,SM,AN,NT,FQ), whereas CM is the code of the course, SM is the semester, AN is the year, NT the note, and FQ the frequency.

Suppose I have the following fact:

historico(08080808,[item(1,1,2008,3.0,0.77),item(1,2,2008,6.5,0.90),item(5,1,2009,8.0,0.80)]).

I need to produce the list of names of extra curricular subjects taken by the student, whose RA will be provided (the course code to be considered will be given in a second parameter and the produced list must be returned in a third parameter); intended execution:

extra(08080808,1,QUAIS).

QUAIS = [anatomia] (considerando que existe uma materia(5,anatomia,6). )

I have the following rules already created:

curso(CODIGOCURSO,NOMECURSO).

materia(CODIGOMATERIA,NOMEMATERIA,CREDITOSMATERIA).

curriculo(CODIGOCURSO,[CODIGOMATERIA1,CODIGOMATERIA2,...,CODIGOMATERIAn).

aluno(RA,NOME).

cursa(RA,CODIGOCURSO).

historico(RA,[ITEM1,ITEM2,...,ITEMn).  (como mostrei anteriormente).

How can I do the job extra(RA,CODIGOCURSO,LISTAMATERIAS) ? I intend to compare each item of the student’s history with the subject and curriculum. But how to go through the list of items in the student’s history?

Answer 1

There are two ways to go through a list, the most "natural" - using recursion, which you probably already know - or through a combination of member with findall/bagof/setof. I will show both forms, as they have advantages and disadvantages (in legibility, mainly, and maybe in the performance).

Recursion

Firstly, it is necessary to determine whether the matter M belongs to the course C:

pertence_curso(M,C) :-
    curriculo(C,Lista),
    member(M, Lista).

Then, if you go through all the subjects of the student checking if they belong to the course or not; if it belongs, it is included in the list, otherwise you "jump" it and go to the next:

extra(Aluno, Curso, R) :-
    historico(Aluno, Itens),
    percorre_itens(Itens, Curso, R).

% Se acabaram os itens, retorna a lista vazia
percorre_itens([],_,[]).
% Se a matéria pertence ao curso, inclui ela no resultado
percorre_itens([item(CM,_,_,_,_)|Resto], Curso, [Materia|Resultado]) :-
    pertence_curso(CM, Curso),
    !,
    materia(CM, Materia, _),
    percorre_itens(Resto, Curso, Resultado).
% Se ela não pertence ao curso (cláusula anterior falhou), não inclui
percorre_itens([_|Resto], Curso, Resultado) :-
    percorre_itens(Resto, Curso, Resultado).

The problem of this method is that it will return repeated results (in your example, the matter 1 was attended in the first and second semester, so she will be included in the final result twice). To get around this, you can either use an accumulator (i.e. start with the empty list, and insert items into it, but only insert if it is no longer there) or do the normal method and at the end delete the repeated items.

Member and setof

The idea behind this technique is to choose not deterministically any element that satisfies the conditions cited, and ask for "more solutions" until all possibilities are exhausted:

materia_extra(Aluno, Curso, Materia) :-
    curriculo(Curso, Materias),
    member(CM, Materias),
    historico(Aluno, Itens),
    member(item(CM,_,_,_,_), Itens),
    materia(CM, Materia, _).

And this is it! I chose a course on the course list, then chose an item on the course list from the student whose code is the same as the chosen course. This predicate will succeed if such a combination exists, and will return only one result (a single matter). If that combination is not found, it will fail.

It’s easy to see that if you call materia_extra in the terminal and asking for "more results" he will deliver you all the materials that satisfy this condition, one at a time. But how to return them all at once, in a list without repetition (i.e. a set)? Therein comes the setof:

extra(Aluno, Curso, Lista) :-
    setof(M, materia_extra(Aluno, Curso, M), Lista).

He will execute the materia_extra/3 as many times as possible and, for each valid result, put the M (specified in the first argument) in the list Lista. In the case of setof it will only do so if the element no longer exists there (the bagof works the same, only it accepts repeated elements; the findall is equal to bagof, but does not fail if there is no result, returning an empty list instead).