-- Sorting a list by selecting a sorted permutation.

-- First, we define the non-deterministic insertion of an
-- element into a list:
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)

-- A list is sorted if all elements are in ascending order.
sorted []       = success
sorted [_]      = success
sorted (x:y:ys) | x<=y = sorted (y:ys)

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

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