我无法理解下面的代码.
如果我有以下输入,有人可以一步一步地解释发生了什么:
append([1,2,3], Lst).
实际上,我不知道如何将1和2作为结果添加到列表Lst中.
append([_], []).
append([H|T], [H|N]) :- append(T,N).
听起来你是Prolog的新手.如果是的话,欢迎!我们来分析一下.
这个不幸命名的函数有两个子句.Prolog会查看这些条款,以便了解哪一条适用.当找到匹配的匹配时,它会尝试执行它.如果某个地方出现故障,它将备份并尝试下一个选项.准确地说,这些选择点根据程序而有所不同; 在这个程序中,唯一一个将在子句级别,决定使用哪个规则.
查看第一条规则的一种方法是它说"具有一个元素的列表,无论该元素是什么,都与空列表相关." 看看append([_], []),如果我们有,X = [foo]并且Y = []它会持有,因为[foo]它是一个单项列表并且[]是空列表.这个规则是很好的Prolog风格,因为无论实例化它都可以工作:我们可以提供左边或右边或两者都没有,这没关系.
第二个条款也很简单.它表示左参数和右参数是相关的,如果它们都以相同的项开始,并且其余列表也与此相同的谓词相关.换句话说,如果我有两个列表X,Y这append(X, Y)是真的,那么append([H|X], [H|Y])也是如此.H是什么并不重要,除了暗示之外,X和Y都无关紧要append/2.
从逻辑上思考,如果我知道任何单项列表与空列表相关,并且任何列表与以相同项目开头的列表相关,并且相同,则可以如此相关的唯一类型的列表是列出每个项目相同的列表,除了左侧列表末尾还有一个项目在右侧不存在.所以[1,2,3,4]与[1,2,3]有关,但[1,2,3,foo]和[1,2,3]也是如此.
在程序上,让我们看一下当使用这组参数处理这个谓词时会发生什么:
append([1,2,3], X).
第一条规则与[1,2,3]不匹配.所以我们必须看看第二条规则:
append([1|[2,3]], [1|X]) :- append([2,3], X).
我们可以重申:
append([2|[3]], [2|Y]) :- append([3], Y).
现在,第一个规则不匹配:
append([3], []).
所以把它们放在一起:
append([1,2,3], [1|X]) implies
append([2,3], X=[2|Y]) implies
append([3], Y=[])
so Y = []
so X = [2]
so the right side is [1,2].
Prolog跟踪将显示基本相同的信息:
?- trace, append([1,2,3], X).
Call: (7) append([1, 2, 3], _G1633) ? creep
Call: (8) append([2, 3], _G1752) ? creep
Call: (9) append([3], _G1755) ? creep
Exit: (9) append([3], []) ? creep
Exit: (8) append([2, 3], [2]) ? creep
Exit: (7) append([1, 2, 3], [1, 2]) ? creep
是什么让这个Prolog代码混淆的是,它看起来并不像你告诉Prolog如何做任何事情.这是真的,你没有,但通过逻辑指定什么是真的,Prolog能够自己解决它.这是非常聪明的代码.如果这是Haskell,我们将讨论内置函数init,它返回所有列表但最后一项.
希望这可以帮助!