<div class="notebook">

<div class="nb-cell markdown" name="md2">
Reference: https://www.reddit.com/r/prolog/comments/1bjg2mv/find_a_list_but_without_a_certain_element/
</div>

<div class="nb-cell program" name="p1">
list_without_ele([], _, []).
list_without_ele([X|Xs], E, Ys) :-
  list_without_ele(Xs, E, Ls),
  ( X = E 
  -&gt; Ys = Ls;
  Ys = [X|Ls]
  ).
</div>

<div class="nb-cell markdown" name="md1">
It's interesting to try some example queries to see what works and what doesn't. Here are some queries that work:
</div>

<div class="nb-cell query" name="q5">
list_without_ele([a, b], a, R).
</div>

<div class="nb-cell query" name="q4">
list_without_ele([a, b], b, R).
</div>

<div class="nb-cell query" name="q1">
list_without_ele([a], E, []).
</div>

<div class="nb-cell query" name="q2">
list_without_ele([a, b], E, [a]).
</div>

<div class="nb-cell markdown" name="md3">
Here's the first query that doesn't seem to work:
</div>

<div class="nb-cell query" name="q3">
list_without_ele([a, b], E, [b]).
</div>

<div class="nb-cell markdown" name="md9">
So let's run the query again, this time with tracing enabled (click "step into" repeatedly):
</div>

<div class="nb-cell query" name="q10">
trace, list_without_ele([a, b], E, [b]).
</div>

<div class="nb-cell markdown" name="md10">
We can show a rough map of how this predicate will execute:

```
( 1) list_without_ele([a, b], E, [b])
( 2)   list_without_ele([b], E, _1)
( 3)     list_without_ele([], E, _2)
( 4)       _2 = []
( 5)     (b = E  -&gt;  _1 = _2  ;  _1 = [b|_2])
( 6)       b = E
( 7)       _1 = []
( 8)   (a = E  -&gt;  [b] = _1  ;  [b] = [a|_1])
( 9)     a = b                                 (fail)
(10)     [b] = [a|[]]                          (fail)
```

I'm using underscore variables to avoid ambiguity when a recursive call binds a new variable to a reused name (like `Ys` or `Ls`).

From the top, evaluation will recurse down until it hits the base case on line 3: `list_without_ele([], _, _2)`. This base case succeeds, binds `_2` to `[]`, and control returns to the caller.

That caller is trying to evaluate `list_without_ele([b], E, _1)`. At this point, `X = b` and `E` is unbound. The `-&gt;/2` predicate evaluates `X = E`, which succeeds (binding `E` to `b`). It then evaluates the "true" branch, `Ys = Ls` (actually `_1 = _2`), binding `_1` to `[]`. It then returns to its caller.

The next caller up the stack is trying to evaluate `list_without_ele([a, b], E, [b])`. At this point, `X = a` and `E = b`, `Ls = []`, and `Ys = [b]` (which came down from the caller). The `-&gt;/2` predicate evaluates `X = E` (`a = b`), which fails. It then evaluates the "false" branch, `Ys = [X|Ls]` (really `[b] = [a|[]]`. Since that's the same as `[b] = [a]`, that also fails, and that causes the whole query to fail.

---

So what's going on? The problem is in how you're using `-&gt;/2`. When you say `X = E`, you *think* you're using it to test a value but you're *actually* establishing a binding. And it's a sticky binding too, since `-&gt;/2` implies a cut after evaluating the condition. As a result, once it decides that it's trying to remove `b` from the list, it will *never* backtrack to instead see if it could remove `a` from the list.

In general, cuts can lead to this kind of behavior. Using cuts incorrectly tends to create one-way predicates which work fine when *some* variables are unbound but not when *other* variables are unbound. These cuts are sometimes known as "red cuts" (as opposed to "green cuts", which don't change behavior and are simply an optimization).
</div>

</div>