inits, tails :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = [] : map (x:) (inits xs)

tails [] = [[]]
tails (x:xs) = (x:xs):tails xs

isPrefixOf, isSuffixOf :: Eq a => [a] -> [a] -> Bool
xs `isPrefixOf` ys = xs `elem` inits ys
xs `isSuffixOf` ys = xs `elem` tails ys

insert :: a -> [a] -> [[a]]
insert x [] = [[x]]
insert x (y:ys) = (x:y:ys) : map (y:) (insert x ys)

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

split :: (a -> Bool) -> [a] -> ([a],[a])
split p = foldr (\x (xs,ys) -> if p x then (x:xs,ys) else (xs,x:ys)) ([],[])

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = quickSort ys ++ x:quickSort zs
 where
  (ys,zs) = split (<x) xs