Prolog: recursively build a list - infinite solutions

Question

I'm completely new to Prolog and have a hard time understanding its unification system. My problem is as follows:

I have a Constraint integer, a Source array and a Target array (both of them are arrays of integers). I'd like to filter the elements in the Source array such that the remaining elements have a counterpart in the Target array so that the difference between the element in the Source array and the element in the Target array is exactly Constraint.

Example: Constraint = 1, Source = [1, 5, 7], Target = [2, 3, 4]. FilteredSource should be [1, 5], because abs(1 - 2) = 1 and abs(5 - 4) = 1. There's no 6 or 8 in Target so 7 is no good.

Depending on the arguments I use I either get wrong results or the query get's in an infinite loop.

So far, I have come up with this:

filterByDistanceConstraint(_Constraint, [], _Target, _).

filterByDistanceConstraint(Constraint, [SourceHead|SourceTail], Target, FilteredSource) :-
    filterByDistanceConstraint(Constraint, SourceTail, Target, NewFilteredSource),
    ( 
        passesDistanceConstraint(Constraint, SourceHead, Target)
    ->  
        append(NewFilteredSource, [SourceHead], FilteredSource),
        filterByDistanceConstraint(Constraint, SourceTail, Target, NewFilteredSource)
    ;   
        filterByDistanceConstraint(Constraint, SourceTail, Target, FilteredSource)
    ).

The passesDistanceConstraint part seems to work ok but I'll include it here for reference:

passesDistanceConstraint(_Constraint, _SourceHead, []) :-
    fail.
passesDistanceConstraint(Constraint, SourceHead, [TargetHead|TargetTail]) :-
    Distance is TargetHead - SourceHead,
    (   abs(Distance) =\= Constraint %test failed
    ->  passesDistanceConstraint(Constraint, SourceHead, TargetTail)
    ;   write('Distance constraint passed for '), write(SourceHead), nl
    ).

I'm quite sure this is a trivial problem but I can't figure it out and I'm pulling my hair off. Thanks for any help!

Answer 1

This should work

filterByDistanceConstraint(_Constraint, [], _Target, []).

filterByDistanceConstraint(Constraint, [SourceHead|SourceTail], Target, FilteredSource) :-
    (   passesDistanceConstraint(Constraint, SourceHead, Target)
    ->  FilteredSource = [SourceHead|NewFilteredSource]
    ;   FilteredSource = NewFilteredSource
    ),
    filterByDistanceConstraint(Constraint, SourceTail, Target, NewFilteredSource).

Note the [] instead of _ in the first rule, and that there is only one recursive call in the second.

The 'filter' programming pattern is implemented in SWI-Prolog by include/3 or exclude/3, but to write in plain Prolog, since member/2 can act as an 'enumerator':

filterByDistanceConstraint(Constraint, Source, Target, FilteredSource) :-
  findall(E, (member(E, Source), member(C, Target), abs(E - C) =:= Constraint), FilteredSource).