Scala中的基本逻辑编程

Question

我有一个有趣的小问题，我需要处理类似以下的逻辑子句：

Rule 1. A, B and C are unique, and are numbers from 1 to 3 (so every number is used).
Rule 2. B < 2
Rule 3. C > 2

现在（假设我刚想出的这个快速示例实际上是有效的:P），很容易看出。

A = 2
B = 1
C = 3

但那只是一个非常牵强的例子。

如果你有20个（或者一万个）规则，并且它们重叠了，该怎么办呢？假设有一个有效的单一答案，并且你以某种方式可以访问这些规则（比如说一个谓词列表）。

是否有一个好的、通用的、直观的解决方案呢？我知道Prolog可以用某些库来解决这个问题，但我的尝试都失败了。我知道我可以暴力地对范围内的所有数字进行排列组合，然后手动检查它们是否符合规则。但那似乎相当糟糕。

- Dominic Bou-Samra

---

谓词的形式是否有任何限制，还是完全随意的？ - Miles Sabin

我猜它们是任意的。但它们必须是有用的 - 也就是说，没有一个约束应该限制另一个已经这样做的地方。 - Dominic Bou-Samra

你可能会对Styla感兴趣，它是一个基于Scala的轻量级Prolog解释器，可以从以下网址获取：http://code.google.com/p/styla/ - Paulo Moura

Answer 1

暴力解决方案

首先，我根据规则1创建了所有可能的输入，这恰好是所有排列组合：

val all = (1 to 3).permutations

然后我定义了剩余的规则：

val rule2 = (a: Int, b: Int, c: Int) => b < 2
val rule3 = (a: Int, b: Int, c: Int) => c > 2

我只是过滤掉不符合所有规则的解决方案：

val solutions = all.
  filter(i => rule2(i(0), i(1), i(2))).
  filter(i => rule3(i(0), i(1), i(2))).
  toList

solutions.toList 打印出唯一有效的解决方案:

List(Vector(2, 1, 3))

请注意，由于排列是惰性生成的，因此此实现并不是非常低效（例如，rule3仅应用于通过rule2的解决方案）。

您可以使用foldLeft（）来应用任意数量的谓词：

val rules = List(rule2, rule3)

rules.
  foldLeft(all)((solutionsSoFar, rule) => 
    solutionsSoFar.filter(s => 
      rule(s(0), s(1), s(2))
    )
  )

Drools

介绍一下Drools 商业规则引擎。只需将所有可能的解决方案作为知识库，使用简洁的 DSL 定义规则即可。

- Tomasz Nurkiewicz

---

这就是我拥有的，几乎逐字逐句（说真的，我们的变量名几乎一样:P）。你如何处理10000个规则？我认为链式过滤器在那里不起作用。 - Dominic Bou-Samra

@DominicBou-Samra：如果您对foldLeft()不太熟悉，可以查看我的更新和关于foldLeft()的文章。 - Tomasz Nurkiewicz

Answer 2

这是一个需要使用约束条件的工作。对于Java来说，有几个约束求解器可供选择。我最喜欢的是JaCoP。它有一个很好的Scala DSL，使得它看起来几乎像Prolog约束。这里是一个典型的SENDMOREMONEY例子：http://www.hakank.org/jacop/SendMoreMoney.scala

- drexin

Answer 3

您可能对这篇博客感兴趣，作者在三篇文章中展示了如何在Scala中进行逻辑编程：

http://ambassadortothecomputers.blogspot.com/feeds/posts/default?alt=rss

- bhericher

---

这是一个更好的链接，从那篇三部分文章的第一部分开始：http://ambassadortothecomputers.blogspot.com/2011/04/logic-programming-in-scala-part-1.html - owensmartin