GNU Prolog - Fact List Search

Question

I should have a brain fart or something like that, but I just can't find a solution to this.

If you have a list, for example:

%country(country, population, capital) country(sweden, 8823, stockholm). country(usa, 221000, washington). country(france, 56000, paris). country(denmark, 3400, copenhagen). %city(city, country, population) city(lund, sweden, 88). city(new_york, usa, 5000). city(paris, usa, 1). city(copenhagen, denmark, 1200). city(aarhus, denmark, 330). city(odense, denmark, 120). city(stockholm, sweden, 350). city(washington, usa, 3400). city(paris, france, 2000). city(marseilles, france, 1000). 

I want to find the second largest populated city, which in this case will be Washington, USA - 3400 people. How could you do this?

Thanks.

Answer 1

A slightly shorter version of the wonderful @sharky:

 second_largest_city(Second) :- setof(Size/City, Country^city(City,Country,Size), Cities), append(_, [_/Second, _], Cities). 

setof combines findall and sort . We collect Size/City pairs so that they are sorted by size automatically. The X^Goal construct introduces an existentially quantized variable X (e.g. & exist; x in first-order logic).

Answer 2

Try this for size:

 second_largest_city(City) :- findall(Size, city(_, _, Size), Sizes), sort(Sizes, SortedSizes), append(_, [Size2, _], SortedSizes), city(City, _Country, Size2). 

Explanation: findall/3 finds the sizes of all city/3 facts that are sorted in ascending order by sort/2 with duplicates removed. The append/3 template call corresponds to splitting the sorted list SortedSizes into two parts; a list of any size ( _ ) and the remainder of the second length ( [Size2, _] ) - this binds the Size2 variable to the second largest city of city/3 facts. Finally, all cities with this size are located among the facts of city/3 and are tied to the exit.

Note. . This will not work properly if your built-in for sort/2 does not remove duplicates, because it leaves open the possibility that city/3 facts with more than one equal maximum returns only the maximum (largest). This implementation, using append/3 to search for the second last element of a sorted list of sizes, also accepts sorted sort/2 numbers in ascending order.

In addition, finally, note that this will not succeed if there are less than two facts city/3 , but this is probably fine, given that the predicate is looking for the “second largest” city, and, strictly speaking, be one if at least two cities of different sizes do not exist in the database. If this is a problem, you can simply write additional sentences for second_largest_city/1 to handle such a case.