Calculating arithmetically in Prolog on lists

Question

we are currently working on the implementation of the predicate reduce, which Needs to take a list L, a binary function F that operates on the elements of L and has neutral element N and maps them to a number E that is obtained by applying F to the elements of L recursively.

Here's our Code so far:

reduce([],F,NEUTRAL,EE).

reduce([H|T],F,NEUTRAL,EE) :-
    Goal =.. [F, H, NEUTRAL, EE],
    call(Goal),
    reduce(T,F,NEUTRAL,EE).

add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

mult(N1,NEUTRAL, EE) :- EE is N1 * EE * NEUTRAL.

the Problem is: to same sample queries such as ?- reduce([], add, 0, R). we just get a boolean (in this case true), to others an error back, which tells us that our Arguments are not properly instantiated. What we actually aim for is a Response like R = 0. (for the example given above).

Hope you can help us, please do not be too complicated as we are Prolog beginners ;)

Answer 1

You need the neutral element to end the recursion. You don't need it at every step. I'd almost say that the neutral element belongs with the operator, not with the reduce. Something like this:

operation_neutral(add, 0).
operation_neutral(mult, 1).

Then, your reduce could look like this:

reduce([], Op, Result) :- operation_neutral(Op, Result).
reduce([X|Xs], Op, Result) :-
    reduce(Xs, Op, R0),
    call(Op, X, R0, Result).

But let's keep it easy for now and do it as suggested in the question. You need the neutral element only if the list of operands is empty, to set your result:

reduce([], _, N, N).

Otherwise, go in the recursion and then apply the operation to the result (and you can use call directly):

reduce([X|Xs], Op, N, R) :-
    reduce(Xs, Op, N, R0),
    call(Op, X, R0, R).

You can see here how to use reduce/4 for example with append/3.

Do you see N inside call? I do not see it, and it doesn't belong there.

For completeness, the two operators:

add(X, Y, R) :- R is X+Y.
mult(X, Y, R) :- R is X*Y.

There is no mention of a neutral element either.

---

By the way: what you have called "reduce" is also known as a "fold" over a list. You could define your reduce/3 in terms of foldl like this:

reduce(List, Op, Result) :-
    operation_neutral(Op, N),
    foldl(Op, List, N, Result).

The recursion and the call both happen inside foldl, you don't need reduce/4 at all.

---

How would you solve this in a procedural language? Using pseudo-code with a C-like syntax, and assuming we have some support for generics, it could go like this:

template <typename A, typename Op>
A reduce(A[] operands, Op op) {
    return reduce(operands, op, 0);
}

template <typename A, typename Op>
A reduce(A[] operands, Op op, int n) {
    if (n == operands.length) return neutral<Op>();
    return op(operands[n], reduce(operands, op, n+1));
}

(apparently if this was indeed C++ we would be using iterators, not an index...)

It is not at all that different from the Prolog version. And if you did it the same way as the foldl above, it would probably look like this:

template <typename A, typename Op>
A reduce(A[] operands, Op op) {
    A x = neutral<Op>();
    for (int n = 0; n < operands.length; ++n)
        x = op(x, operands[n]);
    return x;
}

Again, no mention of the neutral element inside the loop, nor in the call to op().

Answer 2

Based to the comments above and the fact that you're still Prolog beginner, I will try to explain some things that may not be very clear:

What are variables in Prolog and what is instantiation ?

In Prolog variables are whatever starts with Capital letters and the anonymous variables _ (just an underscore defines an anonymous variable which is a variable without a name). Variables in Prolog means means that they could represent anything a list, a string, an atom (...whatever), when you use a new variable it is not instantiated which means it could represent anything but right now it does represent- it hasn't being bind with a list, atom... When you want to instantiate a variable you could do that:

• by using unification =/2 for example X = 2 unifies-instantiates variable X with number 2.
• or by using is/2 only for expressions like X is 2 does the same as above.

Very important is that when a variable in Prolog is instantiated we know what it represents and we can not change for example X =2, X = 3 will fail!! since we know that X binds with 2 and we try to reinstantiate with 3 which fails.

What is =/2, is/2, and what's the difference between these two prediactes ??

• is/2 :it returns the result of an arithmetical expression to an uninstantiated variable. This means that you can use it like: X is 2, or X is mod(Z,Y) but it is important to notice here that whatever is in the expression MUST be instantiated if it is a variable like Y and Z previously. If the expression is not instantiated you will get an instantiation error as in your case. Even simple things like 2 is X+1 will fail with instantiation error if X is not instantiated so don't expect with is/2 to return something like X=1 in previous case which is an obvious answer (but not unique so it would be inconsistent!). Also arithmetic expression means that you could not use something like X is [], to unify X with empty list this would of course fail, so in order to do that use =/2, described below.

• =/2 :This is used to unify a variable (or in general a term) with another term. For example you could use it like: X = 2 to unify X with number 2, or X = [1, 2] to unify X with a list or X = 1 + 2 which will not give 3 but just the term 1 + 2, the last two examples I think clearly shows the difference with is/2.

But then how could we use arithmetic expressions like is/2 but more relational ?

The answer here is library CLPFD (as recommended by @lurker in the comments) all you have to do is place :- use_module(library(clpfd)). in your file and use the operator #= instead of is/2. Now you could try X #= 2, which will instantiate variable X with number 2 or even 2 #= 1 + X and now you get no instantiation error but you get the answer X = 1, so you can see that it is now much more relational.

Now to the question...

I agree with @Boris neutral should not be carried through recursion but declared with the function. Though I will try to keep up with your answer-attempt:

First of all when try to consult a file with your code in swi prolog I get:

Warning: /Users/Desktop/reduce.pl:1:
    Singleton variables: [F,NEUTRAL,EE]

This says variables F,Neutral,EE are singleton it this clause:

reduce([],F,NEUTRAL,EE). 

As you can see you don't use anywhere in this clause for example variable F.

To my opinion the reduce predicate should fail with empty list since you can't do any operation with the neutral element and a function which takes two parameters. So as base case I would define using a list with just one element:

reduce([H],F,NEUTRAL,EE):-
        Goal =.. [F, H, NEUTRAL, EE], 
        call(Goal).

Then as explained above rules like:

add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

will cause instantiation error since in the EE is var and you can't use it in is/2 but even if it was instantiated you couldn't also use it because as explained EE is EE + whatever will not work because you try to reinstantiate a variable..!!

In order to fix it I would try to use another variable for the next recursion and then calculate the result like:

 reduce([H],F,NEUTRAL,EE):-
     Goal =.. [F, H, NEUTRAL, EE], 
     call(Goal).
  reduce([H|T],F,NEUTRAL,EE) :-
     reduce(T,F,NEUTRAL,EE1),
     Goal =.. [F, H, EE1, EE],
     call(Goal).

(Here added a new variable EE1 do the recursive call and then calculate the result based on the Result of EE1 that will be returned from recursive call.)

Now let's test it:

?- reduce([1,2,3,4],add,0,L).
L = 10 ;
false.

?- reduce([1,2,3,4],mult,1,L).
L = 24 ;
false.

One more thing when it gave you the result L=10 by pressing ";" we ask for more answers and returns false since there are no possible answers. The false or true things are just a way that Prolog's toplevel informs you if the predicate succeeds or fails.For example:

?- reduce([1,2,3,4],mult,1,24).
true ;
false.

This states that the above is true and when we ask if there are any other ways that this could be true it returns false... So that's it, after all Prolog doesn't seems to be that bad :) (according to your description).
As an exercise you could try to write the same using CLPFD in order to be more relational and be able to answer queries like: reduce(L,mult,1,24). and maybe @Boris's idea about not carrying the neutral all the way through recursion.

---

EDIT

According to @false suggestion and useful comments I will write a second way using call/N which is clearly better(see comments...):

reduce([H],F,NEUTRAL,EE):-
        call(F, H, NEUTRAL, EE).
reduce([H|T],F,NEUTRAL,EE) :-
        reduce(T,F,NEUTRAL,EE1),
        call(F, H, EE1, EE).

Answer 3

As mentioned in the earlier answers you really want to eliminate your dependency upon call/99 .

Here is something to get you started . It is your original completely dysfunctional code with a different syntax . What I mean is that I hope to present a syntaz alternativ that might be useful to you but the broken semantiiks of the original remain nonchanged .

  % [ reduce , VECTOR , FUNCTION , NEUTRAL , EE ] 

  :- [library(clpfd)] .

  [reduce , [] , F , NEUTRAL , EE] :- ( true ) .

  [reduce , [N|NN] , F , NEUTRAL , EE]
  :-
  (
      [F , N , NEUTRAL , EE] ,
      [reduce , NN , Z , NEUTRAL , EE] 
  )
  .

  [add , N , NEUTRAL , EE] :- ( EE #= EE + N + NEUTRAL ) .

  [mult , N , NEUTRAL , EE] :- ( EE #= N * EE * NEUTRAL ) .

Here is the original for convenient comparison ...

  %

  reduce([],F,NEUTRAL,EE).

  reduce([H|T],F,NEUTRAL,EE) :-
      Goal =.. [F, H, NEUTRAL, EE],
      call(Goal),
      reduce(T,F,NEUTRAL,EE).

  add(N1,NEUTRAL, EE) :- EE is EE + N1 + NEUTRAL.

  mult(N1,NEUTRAL, EE) :- EE is N1 * EE * NEUTRAL.

Answer 4

I hope this partial answer is not too off-topic thus voiding it from inclusion in this discussion .

Regarding the OP statement "to same sample queries such as ?- reduce([], add, 0, R). we just get a boolean (in this case true)" it is important to have a good interpretation of what you mean by "true" . In my opinion it is NOT appropriate to consider that "return value" you identified (.i.e. the (implicit) return value) as having a "boolean" type . This is because with a boolean type >>"false" means the opposite to true<< . In prolog in that particular context (.i.e. with regard to the (implicit) return value) the application of the boolean type expectation does not apply , because in the case of that type and nonalike the boolean type --- >>"false" means something different than "true"<< .