Open list and member

Question

Since I want to avoid cost of append/3, I use difference/open lists.

The problem with an open list however is that member/2 reacts with an open list by adding the element to the tail. For example:

?- L=[a|_],member(b,L).
L = [a, b|_G1196] ;
L = [a, _G1195, b|_G1199] ;
L = [a, _G1195, _G1198, b|_G1202] ;
L = [a, _G1195, _G1198, _G1201, b|_G1205] ;
L = [a, _G1195, _G1198, _G1201, _G1204, b|_G1208] ;
L = [a, _G1195, _G1198, _G1201, _G1204, _G1207, b|_G1211]

This is correct behavior since an open list has an unbounded "tail" and the member/2 function unifies this tail/hole ( variable) with the first argument of member.

I'm looking however for a way I can check if there is an element in the open list that is equal to the given element. How can I do this?

Willem Van Onsem · Accepted Answer · 2016-06-07T12:03:51.277

3

You could write your own version of member/2: member_open/2:

member_open(_,X) :-
    var(X),
    !,
    fail.
member_open(X,[X|_]).
member_open(X,[_|T]) :-
    member_open(X,T).

or a more purer aproach:

member_open(X,Y) :-
    \+var(Y),
    Y = [X|_].
member_open(X,Y) :-
    \+var(Y),
    Y = [_|T],
    member_open(X,T).

The Predicate makes the assumption that an open list has a tail that is var/1. If the predicate finds such a tail, it performs a cut (!) and fails.

Demo:

?- member_open(a,[]).
false.

?- member_open(a,[a]).
true ;
false.

?- member_open(a,[a,a]).
true ;
true ;
false.

?- member_open(a,[a,a|_]).
true ;
true ;
false.

?- member_open(b,[a,a|_]).
false.

?- member_open(X,[X,a|_]).
true ;
X = a ;
false.

?- member_open(X,[c,a|_]).
X = c ;
X = a ;
false.

edited Jun 07 '16 at 12:03

answered Jun 07 '16 at 11:17

Willem Van Onsem

443,496
30
428
555

ok, thanks. Please say me one thing: Is it pure in the sense of prolog/logical programming paradigm? I have no experience in that paradigm and such thing are problematic for me – Gilgamesz Jun 07 '16 at 11:46
2

@Gilgamesz: A problem is that there is [no generally accepted definition](https://www.w3.org/2005/rules/wg/wiki/Pure_Prolog.html). But since it uses a cut, it probably is not. You can however rewrite it to a "*more purer*" (between quotes) variant. Although `var` can be considered non-pure as well... If your definition is rather strict, I think it is impossible to implement such `member_open/2` predicate. – Willem Van Onsem Jun 07 '16 at 12:01
3

This is definitely **not** a logical relation, since for example:`?- member(E, Ls).` **fails** (declaratively, this means: there are *no solutions*), but a *more specific* query **succeeds**, for example: `?- member(E, [E|_]).`. From pure logical relations, we *certainly* expect that if a specific query succeeds, then a *more general* query *does not fail*. – mat Jun 07 '16 at 12:09
1

@mat: I agree, so this probably implies it is impossible to write a logical `member` relation such as specified in the question? After all a list with an open tail is more general than the same list with a closed tail. – Willem Van Onsem Jun 07 '16 at 12:13
2

The question itself even cites a logical version of it: The well-known `member/2` predicate is perfectly pure and true **iff** the element is a member of the list. – mat Jun 07 '16 at 12:16
@mat, I thought so. Please help me solve my problem in logical way. – Gilgamesz Jun 07 '16 at 14:08
2

A logical way is to simply use `member/2`. Other ways, if you cannot make a sound decision at the current point in time, include throwing an `instantiation_error`, or using **constraints** to delay the decision. See for example `freeze/2` and how it is used in Ulrich Neumerkel's `library(pio)`. Looking at a variable and just committing to "that variable will never be instantiated to something" is definitely impure to the extreme, and you cannot expect to obtain sound relations as long as you are doing this. – mat Jun 07 '16 at 14:15
"A logical way is to simply use member/2" But how to do it with open list? "or using constraints to delay the decision. " What do you mean? – Gilgamesz Jun 07 '16 at 14:20
3

The declarative meaning of `member(E, Ls)` is: `E` occurs in the list `Ls`. This definitely also works for open lists, with exactly the same meaning. So, you can use `member/2` to express this. I think you should take a step back and reconsider why you are actually using open lists in the first place. If you only want to avoid the cost of `append/3`, simply *prepend* elements, using for example `Ls = [E|Ls0]`. This is in *O(1)*. – mat Jun 07 '16 at 14:27
1

@mat well, under the *question's* semantics, `member(E, [E|_])` is *not* a "more specific version of" `member(E, Ls)`, because the latter means "`E` is a member of an *empty* list `Ls`" and the first means "`E` is a member of a singleton list with `E` as its head", isn't it? – Will Ness Jun 07 '16 at 19:44
2

So, talking about "open" lists is a priori incompatible with any logical reading of a program *at all*, since it means explicitly talking about a state of acquiring a knowledge whereas a logical relation is about a knowledge. Or in FP terms it introduces *time* back into the timelessness of *"the pure"* (now it's not instantiated, and at the *next moment* it is). IOW any desire to prevent `member(1,X)` from succeeding is a priori non-logical. – Will Ness Jun 07 '16 at 19:55
I think the final parts of your comment sum up the situation nicely: You cannot expect to retain pure properties when you use extra-logical predicates to reason about instantiations, such as `var/1`, and then commit prematurely to one of several still possible instantiations. But there are still ways to combine purity with open lists, using for example constraints to denote and store pending goals. `library(pio)` does this, further instantiating on demand. – mat Jun 07 '16 at 19:57
@mat OTOH [here](http://stackoverflow.com/a/20092493/849891) I use open-ended lists but I think the program is still logical (it's a zebra puzzle). What am I missing?... Maybe it can be adapted to work here... – Will Ness Jun 07 '16 at 20:01
This example uses almost only pure predicates (replace `memberchk/2` by `member/2` and it's entirely pure), so that's rather a logic program *par excellence*. – mat Jun 07 '16 at 20:04
@mat `memberchk` is the key to it working. is it not considered pure? (I can never tell). But the relation as a whole *is* logical........ Maybe *that* is the way to attack this problem here: make knowledge about list's length *explicit*, do not *imply* list's end by non-instatiatedness of its tail, *keep* additional variable holding its *length* (serving same purpose as attribute names in the linked answer). Something like that... Then have queries like `open_member(E,1,Ls)` and `open_member(E,1,[E|_])`. – Will Ness Jun 07 '16 at 20:09

Open list and member

1 Answers1

Linked