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?
>> ?- 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".
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.