寻找算法寻求参数以满足给定函数的回报

Question

我有这个特殊的问题,我还没有解决方案.我认为如果我知道它存在一个相关的算法会有所帮助.

我正在寻找的算法是帮助找到满足函数返回的目标的参数的算法.

例如,a works for b表示为(a,b)

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

函数works将确保它们与布尔值的关系

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

现在我得到了

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

如果我想要这两个绑定是真的,那么这个函数必须为true

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

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

我在考虑回溯,但还不知道如何实现它.如果有人能给我提示,我将不胜感激.

作为旁注,我正在使用函数式编程范例在F#中实现该算法.

Answer 1

您需要向后链接是正确的，杰克是正确的您需要统一，但具体来说您需要通过向后链接进行句法统一。

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

编辑

我在我拥有的一些可用的 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。IE

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

大写字母代表 Prolog 变量。即 XYZ
小写字母代表 Prolog 常量。即 abc

您的作品问题只是经典祖先示例的变体。请参阅：Prolog/递归规则