Perfoming member check on a difference list, but how?

Question

I tried to answer another question (wrongly though) and this led to a question on "difference lists" (or "list differences", which seems a more appropriate name, unless "Escherian Construction" isn't preferred)

We have a fully ground list of elements obj(X,Y) (both X and Y ground). We want to retain only the first obj(X,_) where X hasn't been encountered yet when going through the list front to back. Those "first elements" must appear in order of appearance in the result.

Let's specify the problem through test cases:

% Testing

:- begin_tests(collapse_dl).   

test(one)   :- collapse_dl([],[]).
test(two)   :- collapse_dl([obj(a,b)],
                           [obj(a,b)]).
test(three) :- collapse_dl([obj(a,b),obj(a,c)],
                           [obj(a,b)]).
test(four)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j)],
                           [obj(a,b),obj(b,j)]).
test(five)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j),obj(a,x),obj(b,y)],
                           [obj(a,b),obj(b,j)]).

:- end_tests(collapse_dl).

rt :- run_tests(collapse_dl).

Now, this is easy to implement using filtering, list prepend and reverse/2, but what about using difference lists and list append?

however, I'm not able to get the seen/2 predicate to work. It checks whether obj(A,_) is already in the difference list. But what's a proper termination for this predicate?

% This is called

collapse_dl([],[]) :- !. 
collapse_dl([X|Xs],Out) :-
   Dlist = [X|Back]-Back,        % create a difflist for the result; X is surely in there (as not yet seen) 
   collapse_dl(Xs,Dlist,Out).    % call helper predicate  

% Helper predicate

collapse_dl([],Ldown,Lup):-               % end of recursion; bounce proper list back up
   Ldown = Lup-[].                        % the "back" of the difflist is unified with [], so "front" becomes a real list, and is also Lup                    

collapse_dl([obj(A,_)|Objs],Ldown,Out) :- 
   seen(obj(A,_),Ldown),                  % guard: already seen in Ldown?
   !,                                     % then commit
   collapse_dl(Objs,Ldown,Out).           % move down chain of induction

collapse_dl([obj(A,B)|Objs],Ldown,Out) :-
   \+seen(obj(A,_),Ldown),                % guard: not yet seen in Ldown?
   !,                                     % then commit
   Ldown = Front-Back,                    % decompose difference list   
   Back = [obj(A,B)|NewTail],             % NewTail is fresh! Append via difflist unification magic
   collapse_dl(Objs,Front-NewTail,Out).   % move down chain of induction; Front has been refined to a longer list

% Membership check in a difference list 

seen(obj(A,_),[obj(A,_)|_Objs]-[]) :- !.  % Yup, it's in there. Cut retry.
seen(Obj,[_|Objs]-[]) :- ...              % But now???

Update

With Paulo's code snippet:


% Membership check in a difference list 

seen(Element, List-Back) :-
    List \== Back,
    List = [Element|_].    
seen(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    seen(Element, Tail-Back).

So, term equivalence, or dis-equivalence in this case, is the solution!

We now pass all the test.

score 2 · Accepted Answer · answered Apr 07 '20 at 18:57

2

Try (taken from Logtalk difflist library object):

member(Element, List-Back) :-
    List \== Back,
    List = [Element|_].
member(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    member(Element, Tail-Back).

answered Apr 07 '20 at 18:57

Paulo Moura

18,373
3
23
33

All right, I sort get it.. The key is [term equivalence](https://www.swi-prolog.org/pldoc/doc_for?object=(%5C%3D%3D)/2) ... I have retconned my code to fit this as it had a few other problems. – David Tonhofer Apr 07 '20 at 19:46

Will Ness · Answer 2 · 2020-04-08T11:42:55.450

memberchk/2 should do it. Using the approach from here,

%% collapse_dl( ++Full, -Short )
collapse_dl( [obj(K,V) | A], B ) :-
    memberchk( obj(K,X), B ),
    ( X = V -> true ; true ),
    collapse_dl( A, B ).
collapse_dl( [], B ) :-
    length( B, _), !.

Doing what (functional) Prolog does best, instantiating an open-ended list in a top-down manner.

Passes the tests included in the question.

Addendum: With printouts

%% collapse_dl( ++Full, -Short )
collapse_dl( [obj(K,V) | A], B ) :-
    format("Enter : ~w relatedto ~w\n", [[obj(K,V) | A], B]),
          % Necessarily find  (find or insert)  obj(K, X) (thanks to the 
          %  uninstantiated X) in list B which has an "unobserved" tail:
    memberchk( obj(K,X), B ),
          % Unify X with V if you can; ignore failure if you can't!
    ( X = V -> true ; true ),
    format("Mid   : ~w relatedto ~w\n", [[obj(K,V) | A], B]),
    collapse_dl( A, B ),
    format("Return: ~w relatedto ~w\n", [[obj(K,V) | A], B]).

collapse_dl( [], B ) :-
    format("Termination: From unobserved-tail-list ~w ",[B]),
    length(B, _), 
    format("to ~w (and don't come back!)\n",[B]),
    !.

Because of the added printouts this code is no longer tail-recursive. The original is, and so has no "return" in its trace: it just goes forward and stops working right away when the input list is traversed to its end.

See more about the distinction e.g. here.

This "open-ended list" technique is not difference list, but the two are very closely related. And we don't actually need the explicit tail anywhere here, except for the final freezing. So we just do the O(n) length call instead of the explicit O(1) Tail = [] we'd do with difference lists, no biggie.

Of bigger impact is the choice of list instead of e.g. tree data structure. Trees can be open-ended too, just need to use var/1 here and there. Next step is the tree's structure. Top-down open-leaved tree can't be rotated (as all the calls reference the same top node) so its depth will depend on the input's orderedness. To maintain good balance the trees need to be rotated on occasion, hence closed; and we're back to the traditional state-passing code, were each call gets two tree arguments -- the one before update, and the other after it: the

    upd(T1, T2), next(T2, T3), more(T3, T4), ...

kind of thing. It ought to be used in real code. There are some libraries that do that.

This answer's code is simplistic, in order to be simple and illustrative.

It was this one: https://stackoverflow.com/questions/61079223/prolog-deleting-pairs-with-the-same-first-value-from-list and I solved a different problem (namely, the one in the present question) — David Tonhofer, Apr 08 '20 at 09:04
funny, just now realized it says "member check" in the title. :) — Will Ness, Apr 08 '20 at 09:12
check out the linked one(s) for context. but do ask here, if you feel like it. :) — Will Ness, Apr 08 '20 at 09:12
I can't decide whether this is nearer dirty coding or nearer an LP [Aikido technique](https://www.youtube.com/watch?v=1UjYxpDcMsA). Probably the latter. It's not a difference list though, it's an "unobserved-tail-list", if I understand correctly. — David Tonhofer, Apr 08 '20 at 10:01

score 1 · Answer 3 · answered Jun 30 '21 at 19:07

1

Since I currently need it, I got a simpler solution. Assuming the difference list is open, means for the pair List-Back, we have var(Back). Then we can short cut, only passing List:

member_open(_, List) :- var(List), !, fail.
member_open(Element, [Element|_]).
member_open(Element, [_|List]) :- member_open(Element, List).

If we want to append an element to the List, since for example we didn't find it via member_open/2, we simply make Back = [NewElement|Back2] and continue with Back2.

Here is variables/2 (ISO term_variables/2) written this way, so that it doesn't need reverse/1:

variables(T, L) :-
   variables(T, B, B, B2),
   B2 = [],
   L = B.

variables(V, L, B, B) :- var(V), member_open(W, L), V == W, !.
variables(V, L, [V|B], B) :- var(V), !.
variables(T, L, B, B2) :-
   T =.. [_|A],
   variables_list(A, L, B, B2).

variables_list([T|A], L, B, B2) :-
   variables(T, L, B, H),
   variables_list(A, L, H, B2).
variables_list([], _, B, B).

Seems to work:

?- variables(f(X,g(X,Y),Y), L).
L = [X, Y].

answered Jun 30 '21 at 19:07

`member_open( E, OL) -> Back=Back2 ; Back=[E|Back2]` is the same as just `member(E,OL)`, I think. with open lists, `member` can't fail -- if the element weren't in the instantiated portion, it is added at the tail. so this seems to be doing more work explicitly that would otherwise get done for us behind the scenes.... except that it gives us the handle on the back pointer, in case perhaps it is needed for something... yes building lists top-down seems much better in any language, and it is so easy in Prolog. :) – Will Ness Jul 01 '21 at 12:45
Thats a bold claim. But it is not the same, since member/2 doesn't expose Back, Back2. Also Also member/2 doesn't expose which branch was taken, you could not write variables/2 with member/2. Also member/2 would infinitely often backtrack over the end of an open list, whereas member_open/2 doesn't do that. – Jul 01 '21 at 13:14
yes, I write about the back pointer, too. as for backtracking, a cut would take care of that (like there is one in member_open's base case clause, too). – Will Ness Jul 01 '21 at 13:38
You wrote an if-then-else with member_open/2 and parameter Back and Back2, and said its the same as member/2. But already the parameters Back and Back2 are missing from the member/2 call. These parameters are also missing if you use once(member(E,OL)). So I don't see any way to fix that. – Jul 01 '21 at 13:54

Perfoming member check on a difference list, but how?

Update

3 Answers3

Addendum: With printouts

Linked