我试图在Haskell中实现列表的排列。排列的想法是这样的：
基本情况是列表长度为0和1（列表本身），当大小为2时，置换给出列表本身以及交换元素。
现在，给定一个列表[a，b，c，d]，我们置换[b，c，d]并附加一个。并且我们将列表更改为第一个中的b，如[b，a，c，d]和permute [a，c，d]等，递归。
到目前为止，我已经在Haskell中完成了以下代码。哪个完美有效。但我对这包含的'haskell-ness'水平并不满意。我想提一些关于如何在haskell中使其更具可读性和效率的提示。提前致谢。代码如下：
-- swap the first element of a list with the element at the index
swapFirstWith index l | index == 0 = l
| otherwise = [l!!index]
++ (take (index-1) (tail l))
++ [head l]
++ (drop (index+1) l)
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations [a] = [[a]]
permutations [a,b] = [[a,b], [b,a]]
permutations lst = foldl (++) [] (map (\x-> miniperms x) swappedList)
where miniperms l = map (\x-> (head l): x) $ permutations (tail l)
swappedList = map (\(i, x) -> swapFirstWith i lst) (zip [0..] lst)
main = do
putStrLn $ show $ perms
putStrLn $ show $ length perms
where lst = [1,2,3,4,5,6,7,8,9]
perms = permutations lst
避免!!,head,tail支持模式匹配。这些函数是部分函数，当列表太短时可能会导致程序崩溃。模式匹配（详尽无遗）没有这样的问题。
length, take, drop通常最好不要使用。
相反，让我们考虑一下简单的递归：
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = doSomething x (perms xs)
如何将perms xs变成perms (x:xs)？在p的每个排列xs中，我们需要在x的任何可能点插入p。我们得到了
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = [ p' | p <- perms xs, (use insert here) ]
在所有点插入的地方如下
insert :: a -> [a] -> [[a]]
insert x [] = [[x]]
insert x (y:ys) = ... -- todo
我将留给您完成代码。
同
picks :: [t] -> [([t], t)]
picks [] = []
-- picks [x] = [([],x)]
picks (x:xs) = [(xs,x)] ++ [(x:ys,y) | (ys,y) <- picks xs]
它是直截了当的
perms :: [t] -> [[t]]
perms [] = [[]]
perms xs = -- [(x:zs) | (ys,x) <- picks xs, zs <- perms ys]
do
(ys,x) <- picks xs -- pick an element, any element
zs <- perms ys -- permute what's left
return (x:zs) -- and put them together
编辑：创建和传递更新域的重复模式表明我们可以做得更好，即使它成为正确的域在我们幕后自动传递，作为这个特定计算模型的“管道”的一部分，原样。
现在我们不得不担心出错，明确命名临时域，并且要特别小心地将正确的变量作为要使用的域传递。为我们自动处理这些担忧是件好事。
使用notions of computation类型的特定实例捕获特定的Monad。
在"unique selection" monad的帮助下Louis Wasserman的回答，
newtype UniqueSel t a = UniqueSel {runUS :: [t] -> [ ([t], a) ] }
-- domain updated_dom, result
instance Functor (UniqueSel t) where
fmap = liftM
instance Applicative (UniqueSel t) where
pure a = UniqueSel (\ choices -> [(choices, a)]) -- unchanged domain
(<*>) = ap
instance Monad (UniqueSel t) where
return = pure
m >>= k = UniqueSel (\ choices -> [ r | (cs, a) <- runUS m choices,
r <- runUS (k a) cs ])
我们可以重新编写上面基于列表的do代码作为基于UniqueSel的do代码，
perm = do { x <- UniqueSel picks ; xs <- perm ; return (x:xs) }
所有临时域跟踪变量刚刚消失！我们在这里所做的事情的性质变得更加清晰和明显。没有分心了。
最后一段代码片段不起作用，因为我们不防止从空域中进行选择，这将发生并将有效中止所有计算，最终只产生[]。我们需要返回一个[]作为空域的结果，我们自己。
我们可以在我们的小型独特选择计算语言中引入新的“原始”动作，用choices = UniqueSel (\cs -> [(cs, cs)])将隐藏的选择带入我们的宇宙;并且在空域上分支，比如
perm = do { cs <- choices ; if (null cs) then return [] else
do { x <- UniqueSel picks ; xs <- perm ; return (x:xs) } }
并使用perms = map snd . runUS perm运行我们构建的计算描述;但是这个模式已经在标准库中被捕获，在模块Control.Monad中，作为函数sequence;所以我们可以定义
perms :: [t] -> [[t]]
perms = map snd . (runUS =<< sequence . (UniqueSel picks <$))
-- perms xs = map snd $ runUs (sequence [UniqueSel picks | _ <- xs]) xs
-- = ..... (replicateM (length xs) (UniqueSel picks)) xs
这通过与输入相同长度的选择序列来运行输入。
实际上，为了使n长列表变换，可以使n从不断缩小的可能选择池中任意选择。