listprologprolog-findall

Logically Handling Lists


I have a large number of facts within my program, listing developers and designers in a company, as well as previous projects, like so..

% project(Project Name,Year)
project(efnet, 2007).
% designer(Project Name, Name, Role)
designer(efnet, jane_cole, lead).
% developer(Project Name, Name, Role)
developer(efnet, alex_tobbs, architect).

I have also build a definition that displays a list of either designers or developers working on a project

% employees(Single Project, List of Employees
employees(Project, E)

What I want is to create a new definition that take a list of either designers or developers and displays a list of all the project titles they have BOTH worked on (P); like so..

% projects_of_all(List of Staff, List of Projects)
projects_of_all(S,P):- ...

I can do this easily with findall (or bagof) if I have to find the movies of a single person, but I am not sure how I would do this with a list of the employees. Can someone give me a helping hand with this?


Solution

  • Consider the following which doesn't rely on the all-solutions built-ins like findall, setof or bagof:

    % employees(Single Project, List of Employees
    employees(Project, Employees) :-
        employees(Project, [], Employees).
    
    employees(Project, Acc, Employees) :-
        (   designer(Project, Employee, _)
        ;   developer(Project, Employee, _)
        ),
        \+ member(Employee, Acc), !,
        employees(Project, [Employee|Acc], Employees).
    employees(_Project, Employees, Employees).
    

    This version accumulates a unique list of employees working on a project. Similarly, the implementation of your predicate projects_of_all/2 can be as such:

    % projects_of_all(List of Staff, List of Projects)
    projects_of_all(Employees, Projects):- 
        projects_of_all(Employees, [], Projects).
    
    projects_of_all(Employees, Acc, Projects):-
        \+ var(Employees),
        member(Employee, Employees),
        (   designer(Project, Employee, _)
        ;   developer(Project, Employee, _)
        ),
        \+ member(Project, Acc), !,
        projects_of_all(Employees, [Project|Acc], Projects).
    projects_of_all(_Employees, Projects, Projects). 
    

    Note the guard subgoal \+ var(Employees), as we don't want both arguments to the call to member(Employee, Employees) to be completely unbound, which may cause an infinitely recursive expansion of variables in lists of ever-increasing length. Once we select an Employee, any associated Project is retrieved via designer/3 or developer/3 (leaving choicepoints), until a new Project not yet accumulated is found, at which time we go looking for more; until there aren't any more, in which case we stop (the 2nd clause is the base case).

    While this is probably inefficient relative to any internal (i.e., native, non-interpreted) implementation of findall, setof or bagof, it serves to demonstrate an approach which is intended to help you understand the solution using accumulator methods.

    If you require the use of an all-solutions built-in, you could implement projects_of_all/2 as such:

    % projects_of_all(List of Staff, List of Projects)
    projects_of_all(Employees, Projects):- 
        findall(Project, 
            (   member(Employee, Employees), 
                (   designer(Project, Employee, _)
                ;   developer(Project, Employee, _)
                )
            ), ProjectsBag),
        sort(ProjectsBag, Projects).
    

    Note that setof and bagof will backtrack to give you alternatives, but you want all projects in a list accumulated, which is the behaviour of findall. Presumably, though, you don't want duplicates, so calling sort/2 on the result as shown removes duplicates to give you a set.

    EDIT: The OP changed (clarified) the question after I had written this, which called for a completely different answer (explanation below):

    % projects_of_all(List of Staff, List of Projects)
    projects_of_all(Employees, CommonProjects):- 
        % find the projects of every employee in the input list
        employee_projects(Employees, EmployeeProjects),
        % find the intersection of all projects (common projects)
        recursive_val_intersect(EmployeeProjects, CommonProjects).
    
    employee_projects([], []).
    employee_projects([Employee|Employees], [Projects|Rem]) :-
        findall(Project, 
            (   designer(Project, Employee, _)
            ;   developer(Project, Employee, _)
            ),
        ProjectsBag),
        sort(ProjectsBag, Projects),
        employee_projects(Employees, Rem).
    
    recursive_val_intersect([L|Ls], Intersect) :-
        recursive_val_intersect(Ls, L, Intersect).
    recursive_val_intersect([], Acc, Acc).
    recursive_val_intersect([L0|Ls], L1, Intersect) :-
        intersection(L0, L1, NewL),
        recursive_val_intersect(Ls, NewL, Intersect).
    

    employee_projects/2 is used to build a list of lists of projects that each Employee in the input list had worked on. Note that it uses the findall/3 solution strategy I used earlier. The second predicate, recursive_val_intersect/2,3, determines the intersection of all the project lists, as this indicates the projects that every employee has worked on together. This is different to the above solution which just seeks all projects worked on by all employees in the input list, which is what I'd aimed at.

    Note that recursive_val_intersect/3 above relies on the SWI-PROLOG set-intersection predicate intersection/3, which takes lists with no duplicates (hence the use of sort/2 to construct the input lists in employee_projects/2).