succ 不会在 pred 上被删除

Question

/* Define a Prolog predicate replicate/3 which corresponds to
 * the Haskell function of the same name, except that the numeric
 * argument is expressed symbolically.
 *
 * For example, replicate(s(s(s(0))),a,[a,a,a]) should be satisfied.
 */

到目前为止我已经找到了这个解决方案：

replicate(0,_,[]).
replicate(X,Y,[Y|Z]) :- replicate(p(X),Y,Z).

但问题是 s(s(s(0))) 没有被 pred 函数减少。结果为 p(p(p(s(s(s(0))))))

你们能帮帮我吗？

Answer 1

这是 Haskell 的 replicate 使用（已弃用）n+k 模式编码的：

replicate 0 _ = []
replicate (n+1) a = a : x where x = replicate n a

这直接对应于 Prolog 定义：

replicate(0, _, []).
replicate(s(N), A, [A | X]) :- replicate(N, A, X).

我们只是将结果移动到参数列表中，并将其作为谓词的最后一个参数：

    x = replicate n a    ----->     replicate(N, A, X).

模式匹配是一样的。不同之处在于 Prolog 不是一种面向表达式的语言。没有表达式在被用作下一个 function call 中的参数之前得到评估；取而代之的是，有些术语总是被自动引用，按原样用作谓词的参数。

succ 不会在 pred 上被删除

succ not getting removed on pred

list

haskell

prolog

replicate

successor-arithmetics