-- Example of the non-determinism introduction and elimination pattern
-- Sergio and Michael
-- Fri Mar 11 13:01:12 PST 2011
-- Sort using either of two function to compute the minimum of a list
-- The function is selected according to the value of "intro"

import List

intro = False

sort [] = []
sort (x:xs) = y : sort ys
   where y = (if intro then minOfND else minOfD) (x:xs)
         ys = delete y (x:xs)

minOfND l
   | l =:= x++[min]++y
   & (all (min <=) l) =:= True
   = min 
   where x,min,y free

minOfD (x:xs) = aux x xs
   where aux x [] = x
         aux x (y:ys) = aux (min x y) ys

main = sort [3,1,4,8,1,6]