Есть ли логика для всех в clojure.core.logic?

Я пытаюсь решить первую головоломку в книге Смаллиана «Издеваться над пересмешником» с помощью clojure.core.logic не потому, что это особенно сложно, а скорее в качестве упражнения. В загадке говорится, что есть сад с цветами трех цветов: красный, желтый и синий. Каждый цвет присутствует хотя бы один раз, и независимо от того, какие три цветка вы выберете, среди них будет красный и желтый. Вопрос: третий обязательно должен быть синим?
Базовый скелет логического кода довольно прост:

(run 5 [flowers]
   (counto flowers 3)
   (containso flowers [:red :yellow])
   (fresh [garden]
          (containso garden [:red :yellow :blue])
          (containso garden flowers)
          (forall [flower-selection] (...))))

counto и containso реализованы вручную и делают очевидную вещь. Я новичок в этом, поэтому может быть существующая поддержка библиотек, которую мне не хватает. Важная строка начинается с forall. forall - это в основном то, что я хотел бы, но не могу найти. Единственная известная мне конструкция, которая может быть здесь, это fresh. Но fresh по существу выполняет экзистенциальную квантификацию ∃. Здесь мне нужна универсальная количественная оценка ∀.
Меня не интересует сад, для которого возможно выбрать три цветка, содержащие красный и желтый цвет. Меня интересует сад, который обязательно приводит к такому выбору.


person Sebastian Oberhoff    schedule 13.06.2017    source источник
comment
all ? возможно - найдено здесь github.com/clojure/core.logic/wiki/Examples-(наверное нет)   -  person birdspider    schedule 13.06.2017


Ответы (1)


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

И даже если бы вы сделали это, вы все равно не сделали бы этого, потому что вы только доказали, что существует один сад, который удовлетворяет этому свойству: вы не доказали, что все сады, удовлетворяющие начальным условиям, также удовлетворяют свойству.

core.logic — это «просто» способ моделирования задач поиска, который упрощает удаление неинтересных поддеревьев пространства поиска. Если вы пытаетесь доказать универсальное утверждение о бесконечном пространстве поиска, вам потребуется каким-то образом сократить максимальный размер пространства поиска. Я не вижу очевидного способа сделать это в core.logic для этой проблемы, за исключением того, что нужно еще немного подумать об исходной проблеме, что, конечно же, приведет прямо к решению, вообще не нуждаясь в core.logic.

person amalloy    schedule 13.06.2017
comment
Вы читали «Издеваться над пересмешником»? Мне любопытно, порекомендуете ли вы это; Кроме того, если есть какие-либо книги, похожие на эту, я хотел бы услышать любые рекомендации, которыми вы могли бы поделиться. - person Josh; 13.06.2017
comment
Несомненно, любая из книг Рэймонда Смаллиана хороша для понимания логического мышления, и, в частности, в TMaM есть длинный раздел, посвященный основам функционального программирования. Я не думаю, что когда-либо закончил одну из его книг: головоломки становятся слишком сложными для меня. Однако я не думаю, что они особенно связаны с логическим программированием. Кроме того, на doors.malloys.org я размещаю случайно сгенерированную игру-головоломку (не написанную мной) на основе головоломки в «Женщине или тигре», которые я предлагаю вам попробовать. - person amalloy; 13.06.2017
comment
Отлично, спасибо за информацию, и я попробую головоломку, которую вы предлагаете! - person Josh; 13.06.2017
comment
Может оказаться возможным реализовать предикат Пролога forall/2 в ядре. логика, но я еще не видел ее реализации. - person Anderson Green; 27.06.2018