What problems does curry's choice solve?

Question

I am familiar with what choice operator ((?)) does, it takes two arguments and matches to both of them. We could define it as follows:

a?_=a
_?b=b

This can be used to introduce non-determinism between two values. However what I don't understand why we would want to do that.

What would be an example of a problem that could be solved by using (?)?

Answer 1

One example that is typically used to motivate non-determinism is a function that computes all permutations of a list.

insert e []     = [e]
insert e (x:xs) = (e : x : xs) ? (x : insert e xs)

perm []     = []
perm (x:xs) = insert x (perm xs)

The nice thing here is that you do not need to specify how you want to enumerate all lists, the search algorithm that underlies a logic programming language like Curry (per default it's depth-first-search) does the job for you. You merely give a specification of how a list in your result should look like.

Hopefully, you find some more realistic examples in the following papers.

New Functional Logic Design Patterns
Functional Logic Design Patterns

Edit: As I recently published work on that topic, I want to add the application of probabilistic programming. In the paper we show that using non-determinism to model probabilistic values can have advantages to list-based approaches with respect to pruning of the search space. More precisely, when we perform a query on the probabilistic values, i.e., filter a distribution based on a predicate, the non-determinism behaves less strict that an list-based approaches and can prune the search space.