Pascal's triangle in prolog with recursion and without cuts

Question

I am trying to write a program in prolog that returns a list of Pascal's triangle. The list contains all elements of the row indicated by user input. So for example:

ptriangle(3,X).

returns: X = [1, 2, 1]

So far I have:

sumC([X,Y],[Z]) :- Z is X + Y.
sumC([X,Y|L], Z):- H is X + Y,
                    sumC([Y|L],L2),
                    Z = [H|L2].

ptriangle(1,[1]) :- ! .
ptriangle(2,[1,1]) :- !.
ptriangle(N, L) :- Ant is N - 1,
                   ptriangle(Ant,L2),
                   sumC(L2,R),
                   append([1|R],[1],L), !.

But I am trying to find a way to do this without ! and with recursion. Do you have any suggestions?

Answer 1

You are already using recursion in ptriangle. And you can avoid the cut !, at a cost of some non-determinism.

Take a look at this and see the changes:

sumC([X,Y],[Z, 1]) :- Z is X + Y.
sumC([X,Y|L], Z):- H is X + Y,
                   sumC([Y|L],L2),
                   Z = [H|L2].

ptriangle(1,[1]).
ptriangle(2,[1,1]).
ptriangle(N, [1|R]) :- N > 2,
                       Ant is N - 1,
                       ptriangle(Ant,L2),
                       sumC(L2,R).

That append at the end might become costly, so you can ask sumC itself to give one when it is building the list.

Try to work out how the changes affect the execution.

PS:

sumC([X,Y|L], [H|L2]):- H is X + Y,
                        sumC([Y|L],L2).

is an idomatic way of writing this:

sumC([X,Y|L], Z):- H is X + Y,
                   sumC([Y|L],L2),
                   Z = [H|L2].