Recursively defined function of two integers in Prolog (partition function)

Question

I swear this isn't a homework problem. I haven't attended classes in decades. Once upon a time I came up with a cute recursive formula for the partition function:

         / 0 (k > n)
f(k, n) {  1 (k = n)
         \ p(k, n-k)+p(k+1, n) (k < n)

I thought to try to represent this in prolog. This is about as far as I could get:

partition(N, N, 1) :- !. %% http://stackoverflow.com/a/9582409

partition(K, N, 0) :- K > N.

partition(K, N, A+B) :-
 X is K+1,
 Y is N-K,
 partition(X, N, A),
 partition(K, Y, B).

?- partition(1, 10, X). gives me this:

X = 1+0+0+0+0+1+(1+0+0)+(1+0+0+0+(1+0))+(1+0+0+0+1+(1+0+0)+(1+0+0+1+(1+0+1)))+(1+0+0+0+0+(1+0)+(1+0+0+1)+(1+0+0+0+(1+0)+(1+0+0+(1+0)))+(1+0+0+0+1+(1+0+0)+(1+0+0+1+(1+0+1))+(1+0+0+0+(1+0)+(1+0+0+(1+0))+(1+0+0+1+(1+0+1)+(1+0+0+(1+0)+(1+0+1+(1+0+(1+1)))))))) ?

One thing that's comforting is that there are indeed 42 ones in the above expression(?). I was hoping for X=42. Note the question mark. Yes, there are more matches (apparently infinitely more). The second one is:

X = 1+0+0+0+0+1+(1+0+0)+(1+0+0+0+(1+0))+(1+0+0+0+1+(1+0+0)+(1+0+0+1+(1+0+1)))+(1+0+0+0+0+(1+0)+(1+0+0+1)+(1+0+0+0+(1+0)+(1+0+0+(1+0)))+(1+0+0+0+1+(1+0+0)+(1+0+0+1+(1+0+1))+(1+0+0+0+(1+0)+(1+0+0+(1+0))+(1+0+0+1+(1+0+1)+(1+0+0+(1+0)+(1+0+1+(1+(0+0)+(1+1)))))))) ?

Answer 1

I swear this isn't a homework problem. I haven't attended classes in decades.

Calm down, even if it is homework, there is no problem with asking for help given you have done reasonable effort (reasonable is of course subjective, but I think it is ok for the question) yourself and it is more that there is a specific problem with your implementation :).

The problem with your approach is that you - among many - think that Prolog attaches semantics to functors. For Prolog + is not plus, nor it add things together, + is simply a symbol, it does not evaluate it.

There is however a predicate that evaluates expression trees and uses "semantics" most people agree upon. That is the is/2 predicate. So now you can simply modify it to:

partition(K, N, C) :-
    X is K+1,
    Y is N-K,
    partition(X, N, A),
    partition(K, Y, B),
    C is A+B.

Yes, there are more matches (apparently infinitely more).

That's because your last clause has no guard that says K < N, in other words Prolog will backtrack and regardless on how K and N relate to each other, it can always pick the last clauses (except for K == N since there you placed a cut (!)).

You better use a "guard" for your last clause since otherwise it can be called if K < N when backtracking so. So the full code sequence would read something like:

partition(N, N, 1) :- !. %% http://stackoverflow.com/a/9582409

partition(K, N, 0) :- K > N.

partition(K, N, C) :-
    K < N,
    X is K+1,
    Y is N-K,
    partition(X, N, A),
    partition(K, Y, B),
    C is A+B.

Note that there is nothing special with is/2: it is simply a predicate: you could have called it with is(C,A+B) as well. It only is defined in such a way it can be used as infix operator as well.

With the given clauses, the query gives:

?- partition(1, 10, X).
X = 42 ;
false.