Haskell perm函数修复求助：含重复元素列表的排列问题

原代码的问题在于使用filter移除所有与x相等的元素，导致处理重复元素时错误地清空了剩余列表。比如输入[1,1]时，每次选取x后，filter (\elem -> elem /= x) lst会把两个1都删掉，剩余列表为空，最终生成的排列长度不对。

修复思路 #

需要替换过滤逻辑，改为移除列表中第一个出现的x，而非所有x。可以先实现一个辅助函数removeFirst来完成这个操作，再修改perms函数的列表推导式。

修复后的代码 #

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

perms :: Eq a => [a] -> [[a]]
perms [] = [[]]
perms lst = [x:xs | x <- lst, xs <- perms (removeFirst x lst)]

验证效果 #

• 输入[1,1]时，第一次选取第一个1，removeFirst 1 [1,1]返回[1]，perms [1]生成[[1]]，拼接后得到[1,1]；第二次选取第二个1，removeFirst 1 [1,1]同样返回[1]，拼接后得到另一个[1,1]，最终输出[[1,1],[1,1]]，符合预期。
• 输入[1,2,3]时，removeFirst的效果和原filter一致，仍能正确生成所有全排列。

内容的提问来源于stack exchange，提问作者Roni