-- linear implementation of reverse using an accumulating argument
rev :: [Int] -> [Int] -> [Int]
rev xs = iter xs []
where
iter [] rxs = rxs
iter (x:xs) rxs = iter xs (x:rxs)
-- insert at arbitrary position
insert :: Int -> [Int] -> [[Int]]
insert x [] = [[x]]
insert x (y:ys) = (x:y:ys) : map (y:) (insert x ys)
-- compute all permutations
perm [] = [[]]
perm (x:xs) = concat (map (insert x) (perm xs))