Comment by idle_zealot 17 hours ago
I'm unfamiliar as well, but my best guess is that it relies on non-determinism. i.e. both definitions of 'insert' might be valid, and the runtime chooses which to use at random, resulting in either x or y being prepended to the returned list.
Does this definition somehow cause all random permutations of a given list? The definition of "Some Permutation" seems to imply it can be used any place you need to try any/all permutations, one at a time? At the least, repeated calls to this would be different permutations?
quick Prolog example because I'm not as familiar with Curry:
% This generates or recognizes any palindrome: pal --> [_]. pal --> X,pal,X.
% Here we try it out and press ; to generate more answers. ?- phrase(pal,P). P = [A]; P = [B,A,B]; ...
% Here we plug in a value and it fails with [A], fails with [B,A,B], etc. until it gets to [D,C,B,A,B,C,D], which can be unified with "racecar." ?- phrase(pal, "racecar") true.
Another example is just (X=a;X=b),(Y=b;Y=a),X=Y. This has two answers: X=a, Y=a, and X=b,Y=b. What happens is that it first tries X=a, then moves onto the second clause and tries Y=b, then moves onto the third clause and fails, because a≠b! So we backtrack to the last choicepoint, and try Y=a, which succeeds. If we tell Prolog we want more answers (by typing ;) we have exhausted both options of Y, so we'll go back to the first clause and try X=b, then start afresh with Y again (Y=b), and we get the second solution.
Prolog goes in order, and goes deep. This is notoriously problematic, because it's incomplete. Curry only evaluates choicepoints that a function's output depends on, and only when that output is needed. Curry does have disjunctions (using ? rather than Prolog's ;), unification (by =:= rather than =), and pattern guards rather than clause heads, and the evaluation strategy is different because laziness, but in terms of the fundamentals this is what "non-determinism" means in logic programming. it doesn't mean random, it means decisions are left to the machine to satisfy your constraints.
>> ?- phrase(pal, "racecar") true.
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".
it's not random. it tries definitions in declaration order until one succeeds. it's then yielded as an assignment of variables and control returns to the caller. if that assignment gets contradicted it will backtrack and try the second definition, so on and so forth. it's more like coroutining.