# Does SWI-Prolog avoid redundant searches, and if so how?

**URL:** <https://swi-prolog.discourse.group/t/does-swi-prolog-avoid-redundant-searches-and-if-so-how/4300>\
**Category:** General\
**Created:** [August 16, 2021, 10:20pm UTC](https://swi-prolog.discourse.group/t/does-swi-prolog-avoid-redundant-searches-and-if-so-how/4300 "2021-08-16T22:20:47Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![careyphillips92](https://avatars.discourse-cdn.com/v4/letter/c/71c47a/32.png) [@careyphillips92](https://swi-prolog.discourse.group/u/careyphillips92)\
**Post date:** [August 16, 2021, 10:20pm UTC](https://swi-prolog.discourse.group/t/does-swi-prolog-avoid-redundant-searches-and-if-so-how/4300/1 "2021-08-16T22:20:47Z")

</div>

Consider the two following PL queries:

```prolog
L = [1,2,3], member( X, L ).
L = [1,2,3], member( X, L ), member( X, L ).

```

Would both of them have essentially the same complexity and execution time? Or is the first one O(n) whereas the second is O(n^2)? Does SWI (or any other PL implementation) have logic that avoids a redundant second iteration through the members of L? If so, how is this done?

---

<div class="post-metadata">

**Author:** ![EricGT](https://avatars.discourse-cdn.com/v4/letter/e/f1d935/32.png) [@EricGT](https://swi-prolog.discourse.group/u/EricGT)\
**Post date:** [August 17, 2021, 12:44am UTC](https://swi-prolog.discourse.group/t/does-swi-prolog-avoid-redundant-searches-and-if-so-how/4300/2 "2021-08-17T00:44:39Z")

</div>

> [@careyphillips92](#):
>
> Does SWI (or any other PL implementation) have logic that avoids a redundant second iteration through the members of L?

[clp(fd)](https://www.swi-prolog.org/man/clpfd.html) might do what you are wondering about but it doesn’t do so the way you might think.

> If so, how is this done?

It simplifies the logic based on the constraints and if possible will return all variables grounded, or simplify the expression as much as possible.

* * *

Since your question is a bit open-ended, [tabling](https://eu.swi-prolog.org/pldoc/man?section=tabling) might also be considered a possible answer.

---

<div class="post-metadata">

**Author:** ![peter.ludemann](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/peter.ludemann/32/48_2.png) [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)\
**Post date:** [August 17, 2021, 1:53am UTC](https://swi-prolog.discourse.group/t/does-swi-prolog-avoid-redundant-searches-and-if-so-how/4300/3 "2021-08-17T01:53:46Z")

</div>

You can trace this to see what happens. 😉

In the second query, the first `member(X,L)` will instantiate `X`, so the second `member(X,L)` will simply look for `X` in `L` rather than backtracking through all possibilities. But it’ll still be O(n^2) because the search has to go through all items (`memberchk(X,L)` would stop as soon as `X` is found, so it’d be a bit faster and also wouldn’t leave a choicpoint).

Now, try adding a table/1 declaration and you’ll see a different trace – the table/1 will result in a kind of memoization. In this particular situation, it’s not clear that there’ll be any performance advantage because the memoization will still need to match against the entire `L` list and that’ll be O(n). But for more complex queries, there can be a big performance improvement.