Comment by taeric

1 day ago

This makes it sound like it will always be the same permutation in the sample code, though? Or is the first item of a list not determined? (Or is that not what (x:xs) means? I was reading that as "x followed by more x's".)

1 comment

taeric

klibertp 7 hours ago

See this demo: https://smap.curry-lang.org/smap.cgi?12 - it's described better. Notice, on the left, a drop-down menu showing "PACKS 3.8 /one-value" -> switch this to "/all-values".

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]

and select "/all-values" in the drop down, the result will be:

    [1,2,3,42]
    [1,2,42,3]
    [1,42,2,3]
    [42,1,2,3]

You can see that the system does a depth-first search, so it's not random. This nondeterminism bubbles up to other predicates, so things that use `ndinsert` will also offer multiple solutions.