Comment by idle_zealot
18 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.
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.
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.
3 replies →