The non-determinism comes from `ndinsert` - you'll notice that both clauses can match the same arguments. Normally in such a situation, the first clause will be selected (in Haskell or Erlang, for example). In logic languages, after the first clause matches, the system asks if you want to continue (in the REPL) or automatically calls the next matching clause (/all-values). Now, the second clause is recursive, which again can match either of the clauses. The system will call both, again, providing multiple answers.
If you replace `main = ...` in the example with
main = ndinsert 42 [1, 2, 3]
[1,2,3,42]
[1,2,42,3]
[1,42,2,3]
[42,1,2,3]
Off the top of my head but I think that should be backticks, not double quotes? So that `racecar` is read as a list of characters? I might try it later.
>> Prolog goes in order, and goes deep. This is notoriously problematic, because it's incomplete.
Yes, because it can get stuck in left-recursive loops. On the upside that makes it fast and light-weight in terms of memory use. Tabled execution with memoization (a.k.a. SLG-Resolution) avoids incompleteness but trades off time for space so you now risk running out of RAM. There's no perfect solution.
Welcome to classical AI. Note the motto over the threshold: "Soundness, completeness, efficiency: choose two".