prolog difference list and zipWith

Question

I have a zipWith function:

zipW(_, [], _, []) :-
  !.
zipW(_, _, [], []) :-
  !.    
zipW(F,[H1|T1],[H2|T2],[H3|R]) :-
  X =.. [F, H1,H2, H3],
  call(X),
  zipW(F, T1, T2, R).

It works fine, but now I want to do it for difference lists, so i added

zipW(F, DL-A, DL2-B, NL) :-
  zipW(F,DL,DL2,NL).

But when i run a test

44 ?- A=[1,2,3|X]-X,B=[5,5,5|Y]-Y, zipW(add,A,B,C).

I get an error saying im out of local stack, what am i doing wrong?

Answer 1

First of all, the difference list is nothing but a pairing of an open-ended (usually) list and its ending list-cell/pointer/logvar. For [1,2,3|X], X is its ending list cell, still unassigned/uninstantiated. The point to the pairing is the ability to extend the first part, a list, easily by instantiating the second part, the variable.

After X=[4] the pairing [1,2,3,4]-[4] is still a difference list, but it can't be extended anymore. If we'd use X=[4|Y], the pairing of [1,2,3,4|Y] and Y would become our new difference list.

We don't have to package the two in one compound term, we can just carry the two around in two different arguments to a predicate.

So for your zipWith predicate only the ending condition will change:

zipW(_,L1,Z1,_ ,_ ,L3,Z3) :- L1=@=Z1, L3=Z3, !.  % 1st exhausted
zipW(_,_ ,_ ,L2,Z2,L3,Z3) :- L2=@=Z2, L3=Z3, !.  % 2nd exhausted

the tests succeed both for var,var pair, and for a pair of two equal ground lists, both cases representing an empty difference list.

The working clause is easily amended:

zipW(F, [H1|T1],Z1, [H2|T2],Z2, [H3|R], Z3) :-
      X =.. [F, H1, H2, H3],
      call(X),
      zipW(F, T1,Z1, T2,Z2, R,Z3).

Tested with SWI Prolog:

3 ?- A=[1,2,3|X],B=[10,11,12,13|Y],zipW(plus, A,X, B,Y, C,Z).

A = [1, 2, 3|X]
B = [10, 11, 12, 13|Y]
C = [11, 13, 15|Z] ;

No
4 ?-