Solving a Dungeons and Dragons riddle using Prolog
Very nice!<p>This solution uses the library predicate list_to_set&#x2F;2, relating a (known) list Ls0 of elements to a list Ls <i>without duplicates</i>, where the elements occur in the same order in which they first appear in Ls0. I think it is interesting to consider how such a relation can be described in Prolog, and also <i>how efficient</i> it can be.<p>An immediate solution suggests itself, considering the elements of Ls0 in the order they appear, and keeping track of the elements that have already been &quot;seen&quot;. If an element is encountered that has already been seen, ignore it, otherwise it is part of the list Ls we want to describe. We can use a list to keep track of elements that have already been encountered:<p><pre><code>    list_to_set(Ls0, Ls) :-
            phrase(firsts(Ls0, []), Ls).

    firsts([], _) --&gt; [].
    firsts([L|Ls], Seen) --&gt;
            (   { member(L, Seen) } -&gt;
                []
            ;   [L]
            ),
            firsts(Ls, [L|Seen]).
</code></pre>
This works correctly if the list is ground:<p><pre><code>    ?- list_to_set(&quot;Corvus corax&quot;, Ls).
       Ls = &quot;Corvus cax&quot;.
</code></pre>
Yet, this solution has a very severe drawback: It is worst-case <i>quadratic</i> in the number of elements, and thus not usable for long lists:<p><pre><code>    ?- length(_, E),
       E #&gt; 10,
       N #= 2^E,
       numlist(1, N, Ls0),
       time(list_to_set(Ls0, Ls)).
</code></pre>
yielding:<p><pre><code>       % CPU time: 0.222s
       E = 11, N = 2048, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.880s
       E = 12, N = 4096, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 3.518s
       E = 13, N = 8192, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  ... .
</code></pre>
So, how to improve it? Well, it may be tempting to use for example a <i>hash</i> or an AVL tree to keep track of the &quot;seen&quot; elements, so that it can be more efficiently decided whether an element has already been encountered. And indeed, that is easy to do, and reduces the runtime considerably.<p>For example, using the commonly available library(assoc) for AVL trees, providing <i>O</i>(log(<i>N</i>)) lookup:<p><pre><code>    list_to_set(Ls0, Ls) :-
            empty_assoc(A0),
            phrase(firsts(Ls0, A0), Ls).

    firsts([], _) --&gt; [].
    firsts([L|Ls], A0) --&gt;
            (   { get_assoc(L, A0, _) } -&gt;
                []
            ;   [L]
            ),
            { put_assoc(L, A0, t, A) },
            firsts(Ls, A).
</code></pre>
With this simple change, we get for the query above:<p><pre><code>       % CPU time: 0.034s
       E = 11, N = 2048, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.070s
       E = 12, N = 4096, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.155s
       E = 13, N = 8192, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  ... .
</code></pre>
The most interesting part is that we can do significantly better, by leveraging Prolog&#x27;s <i>logic variables</i> to propagate the information whether elements have already been encountered, yielding a very efficient solution where <i>sorting</i> the list Ls0 (or rather: the list of pairs LVs0, where we associate with each element of Ls0 a logic variable that can be used to propagate information by <i>unifying</i> it with other variables and more concrete terms) dominates the asymptotic complexity:<p><pre><code>    list_to_set(Ls0, Ls) :-
            maplist(with_var, Ls0, LVs0),
            keysort(LVs0, LVs),
            same_elements(LVs),
            pick_firsts(LVs0, Ls).

    pick_firsts([], []).
    pick_firsts([E-V|EVs], Fs0) :-
            (   V == visited -&gt;
                Fs0 = Fs
            ;   V = visited,
                Fs0 = [E|Fs]
            ),
            pick_firsts(EVs, Fs).

    with_var(E, E-_).

    same_elements([]).
    same_elements([EV|EVs]) :-
            foldl(unify_same, EVs, EV, _).

    unify_same(E-V, Prev-Var, E-V) :-
            (   Prev == E -&gt;
                Var = V
            ;   true
            ).
</code></pre>
We now get significantly improved performance:<p><pre><code>       % CPU time: 0.003s
       E = 11, N = 2048, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.006s
       E = 12, N = 4096, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.013s
       E = 13, N = 8192, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  ... .
</code></pre>
And this is indeed how list_to_set&#x2F;2 is implemented for example in Scryer Prolog&#x27;s library(lists):<p><a href="https:&#x2F;&#x2F;github.com&#x2F;mthom&#x2F;scryer-prolog&#x2F;blob&#x2F;fd19128530f68c4623e9df5d0eab6042f62ac8c6&#x2F;src&#x2F;lib&#x2F;lists.pl#L324">https:&#x2F;&#x2F;github.com&#x2F;mthom&#x2F;scryer-prolog&#x2F;blob&#x2F;fd19128530f68c46...</a>