Haskell中如何结合prepend与delete函数实现perm全排列函数

现有可用代码 #

题目给出的两个可正常运行的工具函数如下：

prepend :: Num a => a -> [[a]] -> [[a]]
prepend a l = map (a :) l

delete :: Eq a => a -> [a] -> [a]
delete x [] = []
delete x (y:ys) 
    | x == y    = delete x ys
    | otherwise = y : delete x ys

要求实现的perm函数类型签名为：

perm :: Num a ⇒ [a] -> [[a]]

原有实现的错误点 #

你之前编写的代码：

perm [] = [[]]
perm p = [prepend x xs |  x <- p, xs <- perm (delete x p)]

存在两个核心问题导致无法正常运行：

• 参数类型不匹配：prepend的第二个参数要求是[[a]]类型（排列的集合），但你从递归结果perm (delete x p)中遍历取出的xs是[a]类型（单个排列），不符合prepend的入参要求，逻辑完全错误。
• 嵌套结构未拍平：prepend本身返回[[a]]类型的结果，直接放入列表推导会生成三层嵌套列表[[[a]]]，和perm要求的[[a]]返回类型不匹配。

正确实现方案 #

全排列递归逻辑如下：

1. 递归边界：空列表的全排列只有空列表本身，即[[]]
2. 递归步骤：
   • 遍历列表中每个元素x，作为当前排列的首元素
   • 递归计算删除所有x后剩余列表的全排列集合
   • 调用prepend把x拼接到该集合内所有排列的头部，得到所有以x开头的排列
   • 把所有首元素对应的排列集合拼接，得到最终的全排列结果

修正后的完整代码：

perm :: Num a => [a] -> [[a]]
perm [] = [[]]
perm p = concat [ prepend x (perm (delete x p)) | x <- p ]

效果验证 #

以输入perm [1,2,3]为例，运行输出为：

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

完全符合全排列预期，且全程基于给定的prepend、delete函数实现，满足题目要求。

内容的提问来源于stack exchange，提问作者鶫月海