GNU Prolog — поиск в списке фактов

Должно быть, у меня пукнул мозг или что-то в этом роде, но я просто не могу найти решение этой проблемы.

Если у вас есть список фактов, таких как:

%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).

Я хочу найти второй по величине населенный город, которым в данном случае будет Вашингтон, США, с населением 3400 человек. Как бы вы смогли это сделать?

Спасибо.


rules prolog
person Matt    schedule 15.12.2010    source источник
comment
Как бы вы подошли к поиску самого большого города?   -  person Anon.    schedule 15.12.2010

Ответы (2)


arrow_upward
3
arrow_downward

Чуть более короткая версия отличного ответа @sharky:

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

setof объединяет findall и sort. Мы собираем Size/City пар, чтобы они автоматически сортировались по размеру. Конструкция X^Goal вводит экзистенциально квантифицированную переменную X (например, x в логике первого порядка).

person Fred Foo    schedule 15.12.2010
comment
Чуть более короткая версия однострочника более короткой версии от larsmans: second_largest_city(Second):- setof(Size/City, Country^city(City,Country,Size), [, _/Second|] ). - person gusbro; 15.12.2010
comment
@gusbro: нам нужен предпоследний член Cities, а не второй. - person Fred Foo; 15.12.2010
comment
ой, ты прав. Это будет second_largest_city(Second):- setof(RSize/City, Country^Size^(city(City,Country,Size), RSize is -Size), [, _/Second|]) . На этот раз, наверное, не стоит делать это в одну строчку... - person gusbro; 15.12.2010
comment
Назовите меня старомодным, но я даже не считаю что-то длиннее 80 символов анлайнером ;) - person Fred Foo; 15.12.2010
comment
@ларсманс; Я думал об setof/3, но забыл, что он отсортировал решения, используя sort/2 при создании набора! В любом случае, это решение мне нравится больше - оно не только более лаконичное, но и более эффективное (плюс, я кое-чему научился...) +1 - person ; 15.12.2010
comment
Не уверен, почему я не подумал об этом. Теперь это так очевидно :p - person Matt; 16.12.2010
comment
@Matt: я только что понял, что предполагал, что города имеют разные размеры; не видел, чтобы @sharky так считал. - person Fred Foo; 16.12.2010
comment
@larsmans, да, я это понял, но не думаю, что в данном случае это имеет значение. Я готовлюсь к выпускному экзамену, и это один из тех, которые учитель, вероятно, хотел, чтобы мы использовали что-то вроде этого. В основном потому, что я никогда не использовал sort в прологе или даже findall в этом отношении. - person Matt; 16.12.2010

arrow_upward
4
arrow_downward

Попробуйте это для размера:

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

Объяснение. findall/3 находит размеры всех city/3 фактов, которые отсортированы в возрастающем порядке по sort/2 с удалением дубликатов. Вызов шаблона append/3 соответствует разделению отсортированного списка SortedSizes на две части; список любого размера (_) и остаток длины два ([Size2, _]) — это связывает переменную Size2 со вторым по величине размером города из city/3 фактов. Наконец, все города с этим размером расположены среди city/3 фактов и привязаны к выходным данным.

Примечание. Обычно это не будет работать должным образом, если ваша встроенная функция для sort/2 не удаляет дубликаты, потому что это оставляет открытой возможность того, что city/3 фактов с более чем одним равный максимум вернет только максимум (самый большой). Эта реализация, использующая append/3 для поиска предпоследнего элемента отсортированного списка размеров, также предполагает sort/2 отсортированные числа в порядке возрастания.

Кроме того, наконец, обратите внимание, что это полностью потерпит неудачу, если имеется менее двух city/3 фактов — но это, вероятно, нормально, учитывая, что предикат ищет «второй по величине» город, и, строго говоря, не было бы ни одного, если бы не было действительно как минимум два города в БД с разными размерами. Если это проблема, вы можете просто написать больше предложений для second_largest_city/1, чтобы справиться с таким случаем.

person Community    schedule 15.12.2010
comment
sort/2 не находится в Прологе ISO, но он находится в Прологе Эдинбурга с описанной вами семантикой, которая была основой для стандарта ISO. Было бы странно, если бы Пролог, поддерживающий ISO, имел встроенную sort/2 с какой-либо другой семантикой: я предполагаю, что ее нет. - person Charles Stewart; 15.12.2010
comment
@Charles: SWI, YAP и SICStus имеют sort/2 с предполагаемой семантикой. +1 за этот ответ. - person Fred Foo; 16.12.2010