-- An implementation of permutation sort using list comprehensions:

-- compute the list of all splittings of a list:
splits :: [a] -> [([a],[a])]
splits []     = [ ([],[]) ]
splits (y:ys) = ([],y:ys) : [ (y:ps,qs) | (ps,qs) <- splits ys ]

-- compute the list of all permutations of a list:
perms :: [a] -> [[a]]
perms []     = [[]]
perms (x:xs) = [ ps++[x]++qs | rs <- perms xs, (ps,qs) <- splits rs ]

-- is a list sorted?
sorted []  = True
sorted [_] = True
sorted (x:y:ys) = x<=y && sorted (y:ys)

-- permutation sort:
sort :: [Int] -> [Int]
sort xs = head [ ys | ys <- perms xs, sorted ys ]


goal n = sort [n,n-1..1]
-- Result: [1..n]