Re: Question about difference lists

From: Bart Demoen <bmd@xxxxxxxxxxxxxxxxx>
Date: Thu, 25 Aug 2005 08:18:43 +0200

John Poplett wrote:

% uniq_dl fails in the call to member below
uniq_dl(List,Set) :- uniq_dl(List,Set,[]).
uniq_dl([],Slot,Slot).
uniq_dl([Head|Tail],Set,Slot) :-
        member(Head,Set), % trouble is here.
        !,
        uniq_dl(Tail,Set,Slot).
uniq_dl([Head|Tail],[Head|Slot1],Slot) :-
        uniq_dl(Tail,Slot1,Slot).


If you program with difference lists, the invariant that should
hold is
	I have an openended list
	and I have its (open) tail
That's What your Set,Slot were meant for.
(Slot is a weird name, btw)
However, the goal member(Head,Set) breaks that invariant: you don't get
a new tail from member/2, but you have changed the openended list.
The third clause keeps the invariant, nicely instantiating further the
openended list and returning a new tail (Slot1).
Bottomline: member/2 doesn't cooperate with difference lists well.
But you might use an openended list:

uniq_oel([],Set) :- closelist(Set).
uniq_oel([X|R],Set) :-
        member(X,Set), !,
        uniq_oel(R,Set).

closelist([]) :- !.
closelist([_|R]) :- closelist(R).

Cheers

Bart Demoen
.

References:
- Question about difference lists
  - From: John Poplett

Prev by Date: Re: Psuedo_Newbie: Data Storage?
Next by Date: Re: I now realize WHY my 'consistency check' was pointless: CLP.
Previous by thread: Question about difference lists
Index(es):
- Date
- Thread