succ not getting removed on 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.
 */

So far I've come to this solution:

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

but the problem is that the s(s(s(0))) is not getting reduced by the pred function. it results into p(p(p(s(s(s(0))))))

could you guys help me out?

Answer 1

This is Haskell's replicate coded with the (deprecated) n+k patterns:

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

This directly corresponds to the Prolog definition:

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

We just move the result into the arguments list, and make it the last argument to the predicate:

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

The pattern matching is the same. What's not the same, is that Prolog is not an expression-oriented language. There are no expressions which get evaluated before being used as arguments in the next function call; instead, there are terms which are auto-quoted, always, used as is as arguments to predicates.