Search code examples
haskellprologlist-comprehensionsublistprolog-findall

Translate Haskell to Prolog - finding sublist of sum

I am trying to translate the following Haskell code:

-- sublistSums list sum returns a list of the sublists of list that add up to sum
sublistSums :: [Int] -> Int -> [[Int]]
sublistSums [] 0 = [[]]
sublistSums [] _ = []
sublistSums (x:xs) sum = [x:tailList | tailList <- sublistSums xs (sum-x)] ++
                         sublistSums xs sum

...into Prolog. The code is supposed to give me a list of all the lists whose sum adds up to a target number. For example, 

?- sublistSums([[1,2,3],[4,5,6]],6).

Should give you [[1,2,3]] if it binds because 1+2+3=6.

This is what I have so far: 

sublistSums([], 0) :-
    sublistSums([],0,[]).
sublistSums([], _) :-
    sublistSums([],0,[]).
sublistSums([x|xs], sum) :-
    conc(conc(x,findall(xs,(sublistSums(xs, (sum-x))),List)), sublistSums(xs, sum)).

When I call the sublistSums function, however, it gives me this:

?- sublistSums([[1,2,3],[4,5,6]],6).
false.

I also tried:

sublistSums([], 0, ReList) :-
   [[]].
sublistSums([], _, ReList) :-
   [].
sublistSums([x|xs], sum, ReList) :-
   conc(conc(x,findall(xs,(sublistSums(xs, (sum-x)),ReList),List)), sublistSums(xs, sum, ReList)).

Still gives me the same results. Not exactly sure what I'm doing wrong here.

Solution

  • There are a few elementary issues in your Prolog code:

    • sum is a Prolog atom, so it will never unify with a list.
    • in Prolog, we define relations between entities, and you need predicate arguments to refer to these entities.

    Therefore, you cannot translate the code verbatim. Still, a quite literal Haskell→Prolog translation is possible, if you for example introduce a new argument to hold the original function's return value. Your second snippet goes into this direction, but it is not self-contained, and also contains several mistakes. For example xs and sum are atoms, whereas Prolog variables start with an uppercase letter or with an underscore.

    In addition, if you continue to attempt a literal translation, you will forego the chance to truly benefit from the generality of relations. Typical Prolog predicates can be used not only in one, but in several directions, and you can use them not only to compute, but also to test and to complete partial results.

    Thus, instead of a literal translation, I would like to show you a more idiomatic Prolog solution of this task.

    Our first observation, which is clear from the type signature: We are reasoning over integers. Thus, I recommend you use your Prolog system's CLP(FD) constraints for fully declarative integer arithmetic. See for more information about this feature.

    Second, the task can be seen as "filtering" a list, and for this we use tfilter/3 which is provided by library(reif).

    Here is the complete Prolog solution:

    sublist_sum(Lss0, Sum, Lss) :-
        tfilter(sum_intlist(Sum), Lss0, Lss).

sum_intlist(Sum, Ls, T)  :-
        sum(Ls, #=, Sum0),
        zcompare(C, Sum0, Sum),
        eq_truth(C, T).

eq_truth(=, true).
eq_truth(<, false).
eq_truth(>, false).

    Think of this predicate as relating a list Lss0, a sum, and a second list Lss, such that all requirements you state are satisfied. Note that I do not say which of these arguments are "given", because any of them may be fully, partially, or not at all specified.

    Your example works as required:

    ?- sublist_sum([[1,2,3],[4,5,6]], 6, Ls).
Ls = [[1, 2, 3]].

    This example stays within the confines of the original function: The first and second arguments are fully specified, and the third one is used to represent the "result".

    However, as is typical for Prolog, we can also more general queries, in which not only the "result", but also other parts are left unspecified. Clearly, this is well beyond the scope of functions, and a literal translation of the original code may not have this benefit.

    For example:

    ?- sublist_sum([[1,2,N]], 6, Ls).

    In this case, we have left N unspecified, and ask Prolog to consider all cases that may apply for N.

    In response, Prolog generates the different possibilities, presented as a disjunction:

    N = 3,
Ls = [[1, 2, 3]] ;
Ls = [],
N in inf..2,
-3+_10694#=N,
_10694 in inf..5 ;
Ls = [],
N in 4..sup,
-3+_10662#=N,
_10662 in 7..sup.

    Note how Ls depends on N.

    We can also generalize this further, and leave even the sum unspecified:

    ?- sublist_sum([[A,B,C]], Sum, Ls).
Ls = [[A, B, C]],
A+B+C#=Sum ;
Ls = [],
A+B+C#=_15806,
_15806#=<Sum+ -1,
zcompare(<, _15806, Sum) ;
Ls = [],
A+B+C#=_15806,
Sum#=<_15806+ -1,
zcompare(>, _15806, Sum).

    Again, Prolog enumerates the different cases.

    Moreover, we can specialize the query and use it to test the relation:

    ?- sublist_sum([[1,2,3]], 5, []).
true.

    Here, we have asked: Does this concrete case hold?, and Prolog responds with true, indicating that the relation works exactly as intended in this case.