Main> perm 2 [1,2,3]

[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]

なるほど簡単だ．

追記：
== を使ってるから Eq に属してないといけないんだよね，と話すとI井君がサクっと改良してくれた．
要するに n 番目の要素と，それを取り除いたリストをタプルで持っておけばいいわけです．

revCat :: [a] -> [a] -> [a]

revCat (s:sl) ls = revCat sl (s:ls)

revCat []     ls = ls
take_ :: [a] -> [([a],a,[a])]

take_ ls = take_' [] ls

  where

    take_' sl (l:ls) = (sl,l,ls) : take_' (l:sl) ls

    take_' sl []     = []
takeOne :: [a] -> [(a,[a])]

takeOne ls' = do

  (sl,x,ls) <- take_ ls'

  return (x,revCat sl ls)
permutation :: Int -> [a] -> a

permutation _ []  = [[]]

permutation 1 ls = do x <- ls

                      return [x]

permutation n ls' = do (a,ls) <- takeOne ls'

                       ls_ <- permutation (n - 1) ls

                       return (a:ls_)