模式匹配- Prolog与Haskell

wlwcrazw  于 2022-11-14  发布在  其他
关注(0)|答案(5)|浏览(216)

这不是家庭作业题,而是考试学习指导题。Prolog中的模式匹配与Haskell中的模式匹配有什么区别?
我做过一些研究,阅读它们背后的理论并没有真正给予我对两者有一个坚实的理解。我读到在Prolog中,模式匹配是不同的,因为它有统一变量的能力,因此能够通过解析推导出可能的答案

eg ?- [a,b] = [a,X]
   X = b

现在我不知道如何在Haskell中显示模式匹配。我知道上面在Prolog中显示的相同查询在Haskell中不起作用,因为Haskell不能像Prolog那样统一。我记得在某个地方,要在Haskell中得到相同的答案,你必须通过守卫显式地告诉它。
我知道我很接近理解它,但我需要有人来打破它为我巴尼风格,这样我就可以完全理解它,并解释给一个12岁的孩子。这一直困扰我相当长的一段时间,我似乎找不到一个坚实的解释。
顺便说一句,上面的例子只是向你们展示我到目前为止学到的东西,我实际上是在试图找到答案。我的主要问题与上面的例子无关,而是对两者之间的区别的完整理解。

kmynzznz

kmynzznz1#

Prolog模式匹配是基于统一的,特别是Martelli-Montanari Algorithm(默认情况下,不检查出现次数)。这个算法匹配相同位置的值,将一端的变量绑定到另一端相应位置的值。这种模式匹配可以双向工作,因此在Prolog中,可以同时使用参数作为输入和输出。下面是一个简单的例子,length/2 predicate 。我们可以使用它来(注解解释了查询):

?- 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 pattern matching是一种单向匹配,用于将变量绑定到给定值的不同部分。一旦绑定,它将执行相应的操作(右侧)。例如,在函数调用中,模式匹配可以决定调用哪个函数。例如:

sum []     = 0
sum (x:xs) = x + sum xs

第一个和绑定空列表,而第二个和绑定至少包含1个元素的列表。基于此,给定sum <a list>,结果可能是0x + sum xs,这取决于sum <a list>是否与sum []sum (x:xs)匹配。

4jb9z9bj

4jb9z9bj2#

Haskell中的模式匹配和Prolog的统一之间的差异源于两种语言中变量的根本不同的角色。
在Haskell中,变量持有值。具体的值。这样的值可能还没有被计算出来,甚至可能是⊥,但除此之外它是一个具体的值。在Haskell中,你不能取一个变量,而只能先陈述它的值的一些性质。
因此模式匹配总是意味着一个具体值与一个包含一些变量的模式进行匹配。这种匹配的结果要么是失败,要么是变量绑定到具体值。在Haskell中,这被进一步限制以避免一般比较的需要,这意味着类Eq是为被匹配的项定义的。
在Prolog中,变量可以是一组可能的解。变量可以出现在任何地方,也可以出现在其他值之间的某个地方。统一现在可以确保所述等式仍然成立,并且结果被最优地表示,即计算最一般的统一子。

?- length(L,5).                      
   L = [_A,_B,_C,_D,_E].
?- length(L,5), maplist(=(E),L).
   L = [E,E,E,E,E].

所以Prolog在这里没有用具体的值来回答,比如L = [1,1,1,1,1]L = [[],[],[],[],[]],而是给出了最一般的统一符作为答案,它包含所有这些具体的值。

jq6vz3qz

jq6vz3qz3#

没有人提到以下非常重要的区别。Prolog中的模式匹配对 predicate 的每个子句都进行尝试,即使前面的匹配中有一个成功了(除非被一个 cut 打断)。但是在Haskell中,子句上的模式匹配只进行尝试,直到第一个成功为止。没有其他的选择被尝试(除非匹配被一个 guard 拒绝)。
Prolog的模式匹配建立了最一般意义上的等式约束(有关详细信息,请参见@false的答案)。共享是显式的A=B, A=5也设置B=5。这是可能的,因为Prolog的logvar可以处于尚未设置(即 * 未示例化 *)状态。这使得 * 打结 * 变得容易(实际上是一种基本的编程技术,即 * 差异列表 *)。
在Haskell中,任何变量都只允许在语法层定义一次。在Prolog中,一个logvar也只能被设置一次(没有回溯),但是它可以指向一个不完整的结构(数据),其中的洞由其他还没有示例化的logvar表示,这些logvar可以在以后的任何时间点设置。
在Haskell中,一个用保护递归定义的给定结构会根据访问的需要逐渐充实。在Prolog中,在初始化一个变量之后,任何后续的统一都将变成对术语兼容性的验证,以及可能的进一步(可能是部分的)示例化(显式 *“填充”漏洞)。

xdyibdwo

xdyibdwo4#

再加上LeleDumbo的答案,我们可以说Prolog统一 * 构建 * 术语以及 * 解构 * 它们,而在Haskell中,构建阶段被方便地要求返回值。
当然,这样的特性允许在纯Prolog中使用所谓的“双向” predicate ,例如在DCG中使用的 predicate ,在某些限制下,可以用于解析和生成。

mutmk8jj

mutmk8jj5#

下面是我在Prolog中发现的一个有趣的例子,以支持@chac(+1 btw),提到Prolog的统一是如何“构建”我们昨天在prolog标记中遇到的术语的:

swapPairs([],       []).
swapPairs([X],      [X]).
swapPairs([X, Y|T], [Y, X|R]) :- swapPairs(T, R).

这个 predicate 几乎没有“主体”,它只在其头部使用其参数的统一和递归。
正如@chac和@LeleDumbo所指出的,这是因为Prolog的统一是“双向的”。
下面是《 haskell 的一个温和的介绍》(A gently Introduction to Haskell)中的描述:
Haskell中的模式匹配与Prolog等逻辑编程语言中的模式匹配不同;特别地,它可以被视为“单向”匹配,而Prolog允许“双向”匹配(通过统一),沿着在其评估机制中的隐式回溯。

相关问题