寻找算法以寻找满足给定函数返回值的参数

Question

我有一个问题，目前还没有解决方案。我认为如果我知道相关算法的存在会有所帮助。

我正在寻找的算法可帮助查找满足函数返回的目标的参数。

例如，“a适用于b”表示为“(a，b)”。

Given: [ (a,b); (b,c) ]

works 函数将确保它们与布尔值产生关联。

let works a b -> true
let works b c -> true

现在我被给予了。

[ (a, "x"); ("x", c) ]

如果我想让这两个绑定都是真的，那么这个函数必须是真的。

let works a "x" -> true
let works "x" c -> true

现在我正在尝试编写一个函数/算法来帮助我实现这样的"x" = b

我考虑使用回溯，但还不知道如何实现。如果有人能给我提供一些提示，我将不胜感激。

顺便说一下，我正在使用函数式编程范式的F#实现算法。

- user2431438

---

听起来像是一个约束满足问题。 - Bernhard Barker

Answer 1

你说的需要反向链接是正确的，Jack说的需要统一是正确的，但具体来说，你需要使用带有反向链接的句法统一。

你的问题并不新，但在CS:StackExchange上已经有更详细的回答，标题是如何在纯函数语言中实现Prolog解释器？。

虽然这会让你走上正确的道路，但根据你想要解决的问题，你可能会发现这并不像看起来那么容易。

编辑

我在我拥有的一些工作F#代码上测试了你的示例，它确实有效，但很抱歉，我无法将代码发布给公众。

对于你提供的示例，只需统一而不是反向链接即可完成。

你需要创建事实：

works(a,b).
works(b,c).

和一个查询

works(a,X),works(X,c).

答案是

X = b

如果您想将此扩展到多个人，那么您需要使用反向链接，因为您将不得不创建一个递归的下属规则。

您需要为其创建事实。

works(a,b).
works(b,c).
works(c,d).

和规则

subordinate(X,Z) :- works(X,Z).
subordinate(X,Z) :- works(X,Y), subordinate(Y,Z).

和一个查询

subordinate(a,X),subordinate(X,d).

答案是

X = b,c

你需要创建类型、统一和反向链接算法。你可以选择创建解析器和漂亮的打印机，并在REPL上添加层，但这不是必需的。

事实、规则和查询以人类术语显示，但如果跳过解析器和漂亮的打印机，你将不得不将它们编码为AST。即。

("works", [Const "a", Const "b"]) 

大写字母代表Prolog变量，例如X Y Z。
小写字母代表Prolog常量，例如a b c。
您的“作品”问题只是经典祖先示例的变体。请参见：Prolog/Recursive Rules。

- Guy Coder

Answer 2

您描述的算法是Unification，它是Prolog的基础，而在F#中实现并不困难。

我建议阅读John Harrison的Handbook of Practical Logic and Automated Reasoning（Amazon，Safari Books），第3.9节涵盖了统一算法。去年，我和其他两个F#开发人员将书中的代码移植到了F#，如果您想看看，请访问fsharp-logic-examples。

根据您对问题的描述，您可能可以使用一些简单的约束逻辑编程（CLP）来解决它，但据我所知，尚未有人为F#实现CLP库。 miniKanren和 cKanren是两个流行的、简单的系统示例，如果您有兴趣，我相信它们不会花费太多时间来移植到F#。

- Jack P.