cYn*_*cYn 35 haskell prolog pattern-matching
这不是一个家庭作业问题,而是一个考试学习指导问题.Prolog Vs Haskell中的模式匹配有什么区别？
我做了一些研究,阅读背后的理论并没有真正让我对两者有充分的理解.我在Prolog中看到,模式匹配是不同的,因为它具有统一变量的能力,因此能够通过分辨率推断并吐出可能的答案
eg ?- [a,b] = [a,X]
X = b
现在我不确定如何在Haskell中显示模式匹配.我知道Prolog中显示的上述相同查询在Haskell中不起作用,因为Haskell无法像Prolog那样统一.我记得在Haskell得到相同答案的地方,你必须通过警卫明确告诉它.
我知道我非常接近理解它,但是我需要有人为我打破Barney风格所以我可以完全理解它并向12岁的人解释它.这已经困扰了我很长一段时间,我似乎无法找到一个可靠的解释.
顺便说一句,上面显示的例子只是向你们展示我到目前为止所学到的东西,而我实际上是想找到答案.我的主要问题与上述例子无关,而是完全理解两者之间的差异.
Lel*_*mbo 44
Prolog模式匹配基于统一,特别是Martelli-Montanari算法(默认情况下减去发生的检查).该算法匹配相同位置的值,一侧的绑定变量与另一侧的相应位置的值.这种模式匹配可以双向工作,因此在Prolog中你可以使用参数作为输入和输出.一个简单的例子,length/2谓词.我们可以使用它(注释解释查询):
?- length([],0). % is the length of empty list zero?
?- length([a,b,c],X). % what's the length of list consisting of a,b and c?
?- length(L,5). % give me all lists that have length of 5
Haskell模式匹配是一种单向匹配,将变量绑定到给定值的不同部分.一旦绑定,它就会执行相应的操作(右侧).例如,在函数调用中,模式匹配可以决定调用哪个函数.例如:
sum [] = 0
sum (x:xs) = x + sum xs
第一个总和绑定空列表,而第二个绑定至少一个元素的列表.基于此,给定sum <a list>,结果可以是0或x + sum xs取决于是否sum <a list>匹配sum []或sum (x:xs).
fal*_*lse 13
Haskell和Prolog统一中的模式匹配之间的区别源于两种语言中变量的根本不同.
在Haskell中,变量保持值.具体价值观.这样的值可能不是已经计算还没有,它甚至可能是⊥,但除此之外,它是一个具体的数值.在Haskell中,您不能接受变量,只能首先声明其值的某些属性.
因此,模式匹配总是意味着具体值与包含一些变量的模式匹配.这种匹配的结果是失败或将变量绑定到具体值.在Haskell中,这进一步限制为避免一般比较的需要,这意味着Eq为匹配的术语定义了类.
但是,在Prolog中,变量可能指的是一组可能的解决方案.变量可能出现在任何地方 - 也介于其他值之间.统一现在确保所述均衡仍然成立并且结果以最佳方式表示,即计算最通用的统一者.
| ?- length(L,5).
L = [_,_,_,_,_]
| ?- length(L,5), maplist(=(E),L).
L = [E,E,E,E,E]
所以Prolog在这里不回答具体的值,L = [1,1,1,1,1]或者L = [[],[],[],[],[]]给出最通用的统一者作为包含所有具体价值的答案.
没有人提到以下非常重要的区别.Prolog中的模式匹配是针对谓词的每个子句尝试的,即使先前的一个匹配成功(除非通过剪切停止).但是在Haskell中,只有第一次成功才会尝试匹配子句.没有尝试其他替代方案(除非比赛被警卫拒绝).
Prolog的模式匹配在最普遍的意义上建立了一个等式约束(详见@false的回答).分享是明确的:A=B, A=5设置B=5也是如此.这是可能的,因为Prolog的logvar可能处于尚未设置(即未实例化)的状态.这使得打结很容易(实际上是一种基本的编程技术,即差异列表).
在Haskell中,允许在语法级别仅定义任何变量一次.在Prolog中,logvar也只设置一次(没有回溯),但允许指向不完整的结构(数据),其中的孔由其他尚未实例化的logvar表示,这些日志可以在以后的任何时间点设置.
在Haskell中,根据访问要求逐渐充实了一个用保护递归定义的给定结构.在Prolog中,在变量的初始实例化之后,任何后续的统一都将转变为术语兼容性的验证以及可能的进一步(可能是部分再次)实例化(明确地 "填充"漏洞).
除了LeleDumbo的答案,我们可以说Prolog统一构建术语以及解构它们,而在Haskell中,构建阶段很方便地要求返回值.
当然,这样的特性允许纯Prolog所谓的"双向"谓词,例如在DCG中被利用,具有一些限制,可以用于解析和生成.
这是一个我在Prolog中感兴趣的例子,以支持@chac(+1 btw)提及Prolog的统一"构建"我们昨天在prolog标签中遇到的术语:
swapPairs([], []).
swapPairs([X], [X]).
swapPairs([X, Y|T], [Y, X|R]) :- swapPairs(T, R).
这个谓词几乎没有"身体".它只在其头部和递归中使用其参数的统一.
正如@chac和@LeleDumbo所指出的那样,这是因为Prolog的统一是"双向的".
以下是对Haskell的温和介绍:
Haskell中的模式匹配与Prolog等逻辑编程语言中的模式匹配不同.特别是,它可以被视为"单向"匹配,而Prolog允许"双向"匹配(通过统一),以及其评估机制中的隐式回溯.