How to choose between bagof, setof and findall in Prolog

8
votes

How does one choose between bagof, setof and findall? Are there any important differences? Which is most commonly used and which is the safest? Thanks for your comments/answers.

I checked the SWI-Prolog manual page on findall/3 and found them to be very similar.

2
prologprolog-setof
The link you gave explains findall/3 versus bagof/3. setof/3 is like bagof/3 except it removes redundant solutions (elements in the result list are unique) and it sorts the results in ascending order. – lurker
Short answer: depends what you want to achieve. You might get more useful answers if you describe a concrete use case and compare the three (bagof/3, setof/3, and findall/3) in the context of your use case. – user1812457

2 Answers

7
votes

That's a great question!

I am not attempting to give an exhaustive answer, but I would like to suggest a few lines of thought that can help you to understand these predicates better:

  • Think about which of these predicates are more fundamental in the sense of what can be expressed in terms of what. For example, can you express findall/3 in terms of setof/3? And what about the other way around? This helps to see what you need to provide at least to implement all these predicates.
  • Think about which declarative properties are preserved by these predicates. For example, does the order in which the solutions are found influence the results? For which of these predicates precisely? Can any of these predicates fail? In which cases precisely?
  • Think about the space and time complexity of each of these predicates. Which of these predicates, if any, can be implemented and used more efficiently than others? And at what cost and tradeoffs?

In addition, I recommend you read Richard O'Keefe's book The Craft of Prolog for valuable information about these predicates.

3
votes

an important difference I found between findall/3 and bagof/3, is that the latter doesn't make copies of the terms it accumulates. This can be crucial, for instance, if your list collects attributed variables, like when modelling a problem with library(clpfd).