0

I'm doing some exercises on prolog lists and I've already read this question, and seen the subtract/3 implementation. But I'm still a little bit confused.

Now I want to remove all occurrencies of an element from a given list, and after a few tries I have this: 

% --- del all X occurrences from a list

del_all_X(_, [], _).
% unbinded T2
del_all_X(X, [X|T], T2):-
    del_all_X(X, T, T2).
    %!.  ERROR: see below
del_all_X(Y, [X|T], [X|T2]):-
    dif(Y, X),   % USE this instead of !
    del_all_X(Y, T, T2).

Which gives me this type of output:

25 ?- del_all_X(x, [x,a,b,x,d,e,x,x], X).
X = [a, b, d, e|_G4115].
  • Which is the right way of thinking while binding free variables (like T2 _)?
  • How to have a clean output ?

Answer: del_all_X(_, [], []).

  • Is there a simpler implementation without caling external functions ?

Thanks

EDIT : added corrections and answers in the question and in the code.

Community
  • 1
  • 1
tuxErrante
  • 1,274
  • 12
  • 19
  • 2
    The reason you get the uninstantiated tail in your result is because of your base case, `del_all_X(_, [], _).` which says that if you delete anything from the empty list, you get an anonymous list (`_`). I'm not sure I understand your comment that you want to *unbind `T2`* here since the whole point is to bind `T2` to the result for the given predicate clause. Logically, if you delete any element from the empty list, you are probably wanting it to result in the empty list. So this should be `del_all_X(_, [], ]).`. For more generality, get rid of the cut (`!`) and use the `dif`. – lurker Mar 12 '16 at 15:05
  • Thanks del_all_X(_, [], []). resolved the little issue. What I meant is that from the tutorial I listed above, it's not clear how to manage output variables. I was erroneously thinking that _ in the base case, was where all the output list was stored. – tuxErrante Mar 12 '16 at 15:10
  • I added the ! to eliminate other output cases in which X was still present, I wanted only the complete answer, i.e. the first one. EDIT: You're right it works this way too. – tuxErrante Mar 12 '16 at 15:17
  • 3
    Your definition incorrectly succeeds for `del_all_X(x,[x],[x]).` It should fail. The `dif/2` that you commented out is not superfluous. And, the `!` **is** not appropriate. – false Mar 12 '16 at 15:19
  • @false Could you clarify or send me to some tutorial ? How could a cut in the recursion change the type of input accepted ? Why it is not appropriate? – tuxErrante Mar 12 '16 at 15:33
  • In the new code edit you show, you commented out the cut but left a dangling comma, thus, ERROR. *Which is the right way of thinking while binding free variables (like `_`)?* Unclear what this question means. *Is there a simpler implementation without calling external functions?* Prolog doesn't have *functions*, it has *predicates*. The only thing you're calling outside of your own predicate is `dif/2` and it's a fairly fundamental predicate. Why do you need to avoid calling it? – lurker Mar 12 '16 at 18:51
  • 2
    The reason that cut is "inappropriate" is because it terminates the predicate before all solutions are found in the event that you do a query that has more than one solution. For example, `del_all_X(a, [b,c,a,b,X,c], R).` has more than one solution, but with the cut, you only get one then termination. – lurker Mar 12 '16 at 18:57
  • @lurker the error near the cut it's just indicating I should not use it, it's not a compilation error. With the binding question I mean: how should I think while building the output variable? It's not always straightforward, in the Learn Prolog Now tutorial there's no theoretical explanation. I don't want to use built in predicates just for didactical purposes. The last example you did it's very interesting, but for now I'm good with lists without inner lists or variables. – tuxErrante Mar 12 '16 at 19:06
  • 1
    See [this question regarding `dif/2`](http://stackoverflow.com/questions/13757261/using-or-dif?lq=1). – lurker Mar 12 '16 at 22:47

1 Answers1

1

  • For what I've understood the use of the cut is inappropriate since this could interrupt the growth of the stack tree in unexpected ways, since it avoids unifications of second rule with different values of that already unified by the first rule. learn prolog now - cut

  • The use of dif is essential since it avoids the unification of the second rule when the searched element (Y) is different than the first of the given list (X), in this case calling this elements with different variables isn't enough. The example given by @false clarifies. See Using \== or dif? 

    % With ! and Without dif
[debug] ?- del_all_X(x, [x], [x]).
 T Call: (7) del_all_X(x, [x], [x])
 T Call: (8) del_all_X(x, [], [x])
 T Fail: (8) del_all_X(x, [], [x])
 T Redo: (7) del_all_X(x, [x], [x])
 T Call: (8) del_all_X(x, [], [])
 T Exit: (8) del_all_X(x, [], [])
 T Exit: (7) del_all_X(x, [x], [x])
true .

    Updated version :

    del_all_X(_, [], []).
del_all_X(X, [X|T], T2):-
    del_all_X(X, T, T2).
del_all_X(Y, [X|T], [X|T2]):-
    %  X \== Y 
    dif(Y, X),     
    del_all_X(Y, T, T2).


[debug] 7 ?- del_all_X(x, [x], [x]).
 T Call: (7) del_all_X(x, [x], [x])
 T Call: (8) del_all_X(x, [], [x])
 T Fail: (8) del_all_X(x, [], [x])
 T Redo: (7) del_all_X(x, [x], [x])
 T Fail: (7) del_all_X(x, [x], [x])
false.
Community
  • 1
  • 1
tuxErrante
  • 1,274
  • 12
  • 19
  • 1
    Good. Now check out how easily your final version can be understood **in a declarative way**: If the elements are the **same**, then the element does not occur in the third list. But if they are **different** (`dif/2`), the element **does** occur in the third list. That's what Prolog is all about: Describing **relations** between things. Forget books that focus on traces. They usually lead to code that simply does not work in general. Try to read material that uses Prolog to its full potential, using declarative predicates like `dif/2` and other constraints, which are easy to understand. – mat Mar 13 '16 at 02:06
  • Thanks, that's why I don't like the Learn Prolog Now tutorial, there's too much practice and little theoretical background explanation. But it's fast to read. Could you link me a better resource ? – tuxErrante Mar 13 '16 at 12:28
  • 1
    For better resources, start with [**Features of good Prolog code**](http://stackoverflow.com/a/15710541/1613573), the other [links on false's page](http://stackoverflow.com/users/772868/false) and the [**answers by repeat**](http://stackoverflow.com/users/4609915/repeat?tab=answers) which often show how to solve tasks in a very general way. – mat Mar 13 '16 at 13:03