Haskell中的排列实现

Question

我试图在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

Answer 1

避免!!,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

我将留给您完成代码.