给定替换S和列表Xs，如何将S应用于Xs [英] Given a substitution S and list Xs, how to apply S to Xs

问题描述

假设我有一个替换 S 并列出了 Xs ，其中出现在 Xs 中的每个变量也都出现在 S .我将如何找到列表 S(Xs)，即如何通过将替换 S 应用于列表 Xs 而获得的列表.

Suppose I have a substitution S and list Xs, where each variable occurring in Xs also occurs in S. How would I find the list S(Xs), i.e., the list obtained by applying the substitution S to the list Xs.

更具体地说，我有一组类似的谓词和DCG规则

More concretely, I have a set of predicates and DCG rules that look something like

pat(P)   --> seg(_), P, seg(_).
seg(X,Y,Z) :- append(X,Z,Y).

如果我尝试将模式 P 与带有变量的列表进行匹配，则会收到替换 S :

If I attempt to match a pattern P with variables against a list, I receive a substitution S:

?- pat([a,X,b,Y],[d,a,c,b,e,d],[]).
   X = c,
   Y = e

我想将替换 S = {X = c，Y = e} 应用于具有变量 X 和 Y ，并收到进行替换的列表，但我不确定解决该问题的最佳方法是什么.

I want to apply the substitution S = {X = c, Y = e} to a list Xs with variables X and Y, and receive the list with substitutions made, but I'm not sure what the best way to approach the problem is.

如果在Haskell中解决此问题，我将建立一个从变量到值的有限映射，然后执行替换.等效的方法是在DCG规则中生成变量和值对的列表，然后使用映射图找到所需的列表.但是，这不是一种合适的方法.

If I were approaching this problem in Haskell, I would build a finite map from variables to values, then perform the substitution. The equivalent approach would be to produce a list in the DCG rule of pairs of variables and values, then use the map to find the desired list. This is not a suitable approach, however.

推荐答案

由于不对替换进行修正(不是Prolog对象)，因此您可以将列表绑定到变量，然后由统一来完成其工作:

Since the substitution is not reified (is not a Prolog object), you can bind the list to a variable and let unification do its work:

?- Xs = [a,X,b,Y], pat(Xs,[d,a,c,b,e,d],[]).
Xs = [a, c, b, e],
X = c,
Y = e .

编辑:如果要在替换后保留原始列表，请使用copy_term:

Edit: If you want to keep the original list around after the substitution, use copy_term:

?- Xs = [a,X,b,Y], copy_term(Xs,Ys), pat(Xs,[d,a,c,b,e,d],[]).
Xs = [a, c, b, e],
X = c,
Y = e,
Ys = [a, _G118, b, _G124] .

这篇关于给定替换S和列表Xs，如何将S应用于Xs的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！