list - Haskell 中的置换实现

Question

我试图在 Haskell 中实现列表的排列。排列的想法是这样的:

基本情况是当列表长度为 0 和 1 是列表本身时，当大小为 2 时，排列给出了列表本身以及交换的元素。

现在，给定一个列表 [a,b,c,d] 我们置换 [b,c,d] 并附加 a。并且我们将列表更改为在第一个中包含 b 像 [b,a,c,d] 和置换 [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

我会让你来完成代码。