-- This is an example for the use of non-deterministic operations
-- in a Curry program.

-- We want to sort a list by selecting a sorted permutation.

-- First, we define the non-deterministic insertion of an
-- element into a list. An element can be inserted into a list
-- either at the fron (first rule) or into the tail of a list
-- (second rule).
ndinsert :: a -> [a] -> [a]
ndinsert x ys     = x : ys
ndinsert x (y:ys) = y : ndinsert x ys

-- A permutations of a list can be obtained by non-deterministically
-- inserting the first element into some permutation of the
-- remaining elements
perm :: [a] -> [a]
perm []     = []
perm (x:xs) = ndinsert x (perm xs)

-- Next we define a partial predicate which evaluates to True
-- if the argument list is sorte, i.e., if all elements are in ascending order.
sorted :: Ord a => [a] -> Bool
sorted []              = True
sorted [_]             = True
sorted (x:y:ys) | x<=y = sorted (y:ys)

-- Sorting a list means finding a sorted permutation of it:
sort :: Ord a => [a] -> [a]
sort xs | sorted ys = ys
  where ys = perm xs

-- Sorting an example list:
main = sort [4,1,2,6,5,3]