-- Insert an element into a list (non-deterministically!) insert :: a -> [a] -> [a] insert x ys = x : ys insert x (y:ys) = y : insert x ys -- Return some permutation of a list: perm :: [a] -> [a] perm [] = [] perm (x:xs) = insert x (perm xs) -- Identity on sorted(!) lists: sorted [] = [] sorted [x] = [x] sorted (x:y:xs) | x<=y = x : sorted (y:xs) --sort xs = sorted (perm xs) sort = sorted . perm