我有一个谓词check/3
用作,例如check(A,B,C)
。所有三个参数都是列表:
C
为主列表A
包含具有奇数索引的项B
包含具有偶数索引的项目
例如,
check([1,3],[2,4],[1,2,3,4]) % is true
check([1,2],[3,4],[1,2,3,4]) % is false
我只是想检查一下,而不是创建两个奇偶校验的列表。这是我写的程序:
check( [] , [] , [] ).
check( O , C , [O,_|C] ) :- check(O,C,A).
我试图通过从第三个列表中删除备用元素并将其放在第一个列表中,同时将其余元素放在第二个列表中来解决这个问题。但我发现,如果我将它们进行比较就足够了。但是,如果没有任何算术或内置谓词,我就不知道如何实现它。
要根据元素在列表中的顺序位置(其*索引)将列表C
划分为奇数和偶数元素的列表,如果将列表中的第一个项目计数为奇数(索引为1),这应该是诀窍:
check( [] , [] , [] ) . % the empty list has neither an even nor an odd element.
check( [O] , [] , [O] ) . % a list of length 1 has only an odd element
check( [O|Os] , [E|Es] , [O,E|Xs] ) :- % a list of length > 1 has both an even and an odd element
check(Os,Es,Xs) . % - park them on the respective lists and recurse down.
另一方面,如果你想把第一个项目算作偶数(索引为0),那也没什么不同:
check( [] , [] , [] ) . % the empty list has neither an even nor an odd element.
check( [] , [E] , [E] ) . % a list of length 1 has only an even element
check( [O|Os] , [E|Es] , [E,O|Xs] ) :- % a list of length > 1 has both an even and an odd element
check(Os,Es,Xs) . % - park them on the respective lists and recurse down.
您也可以通过使用一个带有切换指示状态的标志的辅助谓词来完成同样的事情:
check( Os , Es , Xs ) :- % to partition list C into odd and even components...
check( odd , Os , Es , Xs ) . % - just invoke the helper with an appropriate seed value.
check( _ , [] , [] , [] ) . % we're done when we hit the end of the list.
check( odd , [X|Os] , Es , [X|Xs] ) :- % otherwise, place the head of the source list on the odd result list
check( even , Os , Es ,Xs ) . % - and recurse down, toggling state to even.
check( even , Os , [X|Es] , [X|Xs] ) :- % otherwise, place the head of the source list on the even result list
check( odd , Os , Es ,Xs ) . % - and recurse down toggling state to odd.
您会注意到,在上面的示例中,我们为辅助对象设定了odd
的种子,以指示第一个元素的位置为奇数(1-相对)。如果希望第一个元素具有偶数位置(0-相对),只需将种子值切换为even
即可。
但是有一种更简单的方法:在每次递归中,只需切换两个结果列表的位置:
check( [] , [] , [] ) .
check( [X|As] , Bs , [X|Cs] ) :- check( Bs , As , Cs ) .
太好了!
您实际上非常接近。你的第二条应该是:
check([O|Os], [E|Es], [O,E|Rest]) :- check(Os, Es, Rest).
请注意,这并不能保证任何奇怪或均匀的东西,只是第三个列表将由前两个列表中的交替项目组成。它将生成。如果您不能使用算术运算,那么显然就无法保证列表项的算术属性。但这可能不是这里真正想要的。这将满足您的示例查询。
在我看来,这个子句显示了关于Prolog最难理解的事情之一:通过子句的信息流。你可以想象每个变量都像箭头一样被重用:你有一个从第一个参数的第一个项目到第三个参数的一个项目的箭头,还有一个从第二个参数的第一个项目到第一个参数第二个项目的另一个箭头,然后是从所有列表余数到主体的箭头,本质上说"为了证明这种关系,证明它递归地保持在列表的尾部。"这很奇怪,我认为你要么对此感到困惑,要么对头脑中的模式匹配感到困惑。我的变量名可能并不完美,但我怀疑它们比O和C更有助于了解关系。
我敢打赌,如果你看看这个,看看你的,你会自己看到问题,但它们在这里:
check(O, C, ...)
在类型上混淆。O
和C
在这里需要是列表,但在子句的正文中列出项目(好吧,C
不会,但也有问题)check(..., [O,_|C])
表示列表的第一项将是O
,然后是未指定的内容,然后C将是列表的尾部A
是身体中的一个单体,这意味着它实际上没有做任何事情。每当您收到单例警告时,请将变量替换为下划线,并查看它是否仍然有意义。如果没有,你就有误解,可能需要对你的条款进行修改
为了查看列表构造函数,[X|Xs]说X是第一项,列表的其余部分是X。|
运算符从列表的尾部划分项目。因此,如果你处理的是一个平面(单调)列表,左边的所有东西都应该是项目,右边的东西是另一个列表。你也可以只在右边有一件事,但你可以在它前面有几个用逗号分隔的项目(就像你做的那样)。
希望这能有所帮助!