这篇 post 有两个主要的目的:
- 讨论 Prolog 中的匹配, 解释匹配(match)与相等的不同.
- 使用 Prolog 搜索的机制解决一些问题.
##Matching
Prolog 中有三种不同的 term, 分别的 constants, variables 和 complex terms.
接下来我们解释一下两个 terms 是如何匹配的.
当两个 term 含有相等, 或者两个 term 中的变量在被绑定为指定值之后, 两个 term 相等时, 两个 term 匹配.
也就是说, 以下的 term 都会匹配:
- mia = mia.
- 42 = 42.
- mia = X.
- X = Y.
- friends(john,X) = friends(Y,tom).
接下来我们对匹配进行更精确的定义:
- 如果 term1 和 term2 都是常量, 那么只有当两者是相同的原子或者相同的数字, term1 term2 匹配.
- 如果 term1 是变量, term2 是任意类型的 term, 那么 term1 和 term2 匹配, term1 会被绑定为 term2.
- 如果 term1 term2 是 complex term, 那么在下面情况下, 它们会匹配
- 它们含有相同的名字和参数数量.
- 它们对应的参数匹配.
- 变量的绑定是兼容的, 同一个变量不会同时绑定为两个值.
- 两个 terms 只有在上述 3 个条件之一成立时, 才会匹配.
匹配有什么作用呢? 我们可以使用匹配来为我们提供更强大的抽象能力:
vertical(line(point(X,Y),point(X,Z))).
horizontal(line(point(X,Y),point(Z,Y))).
这两行 Prolog 代码并不是规则, 而是事实, 我们可以使用匹配的能力, 写出这两个规则, 这样我们就可以轻易地判断一条直线是否是垂直的或是水平的.
?- vertical(line(point(1,1),point(1,3))).
true
同样我们也可以利用匹配来寻找与某一点构成垂线的点.
?- vertical(line(point(1,1),point(X,4))).
X = 1.
同样我们也可以利用 Prolog 的匹配解决更加复杂更加困难的问题.
现在我们有 6 个单词, 我们需要将它们填入下面的拼图里:
word(abalone,a,b,a,l,o,n,e).
word(abandon,a,b,a,n,d,o,n).
word(enhance,e,n,h,a,n,c,e).
word(anagram,a,n,a,g,r,a,m).
word(connect,c,o,n,n,e,c,t).
word(elegant,e,l,e,g,a,n,t).
我们可以通过 Prolog 得出答案, 只需要将需要满足的条件写在 predicate 里:
crosswd(V1,V2,V3,H1,H2,H3):-
word(V1,_,A,_,B,_,C,_),
word(V2,_,D,_,E,_,F,_),
word(V3,_,G,_,H,_,I,_),
word(H1,_,A,_,D,_,G,_),
word(H2,_,B,_,E,_,H,_),
word(H3,_,C,_,F,_,I,_),
这样我们就可以得到结果:
?- crosswd(H1,H2,H3,V1,V2,V3).
H1 = abalone,
H2 = anagram,
H3 = connect,
V1 = abandon,
V2 = elegant,
V3 = enhance ;
H1 = abandon,
H2 = elegant,
H3 = enhance,
V1 = abalone,
V2 = anagram,
V3 = connect ;
false.
Prolog 中匹配的能力非常强大, 其实它就是对已经有的条件和数据进行搜索, 尝试所有的答案, 最后给出满足条件的所有结果, 能够极大的降低我们的计算量.
转载申请
本作品采用知识共享署名 4.0 国际许可协议进行许可，转载时请注明原文链接，图片在使用时请保留全部内容，可适当缩放并在引用处附上图片所在的文章链接。
Go 语言设计与实现
各位读者朋友，很高兴大家通过本博客学习 Go 语言，感谢一路相伴！ 《Go语言设计与实现》 的纸质版图书已经上架京东，本书目前已经四印，印数超过 10,000 册，有需要的朋友请点击 链接 或者下面的图片购买。
