-- Typical non-deterministic operation:
coin :: Int
coin = 0
coin = 1

-- with free variables:
coinF :: Int
coinF = zeroOne x
 where
  x free

  zeroOne 0 = 0
  zeroOne 1 = 1


----------------------------------------------------------------------------
-- Sorting a list of elements:

-- Non-deterministic list insertion:
insert :: a -> [a] -> [a]
insert x ys     = x : ys -- as first element
insert x (y:ys) = y : insert x ys -- in the tail of the list

perm :: [a] -> [a]
perm []     = []
perm (x:xs) = insert x (perm xs)

-- Identity on sorted lists:
sorted :: Ord a => [a] -> [a]
sorted [] = []
sorted [x] = [x]
sorted (x:y:zs) | x<=y = x : sorted (y:zs)

sort :: Ord a => [a] -> [a]
--sort xs = sorted (perm xs)
sort = sorted . perm

-- Not every permutation needs to be computed:
-- sort [7,6,5,4,3,2,1] --> sorted (perm [7,6,5,4,3,2,1])
-- -->* sorted (7 : 6 : perm [5,4,3,2,1]) -> failed