Haskell 的 "permutations"函数定义很奇怪

Question

如果我想找到列表的排列，我知道排列的数量由多项系数给出。例如，“MISSISSIPPI”有 11 个字母，“S”出现 4 次，“I”出现 4 次，“P”出现两次，“M”出现一次。因此“MISSISSIPPI”的排列数等于 11!/(4!4!2!) = 34650。

如果我加载 GHCi 并写入:

ghci> import Data.List
ghci> permutations [1,2,3]

它会回来

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

正如预期的那样。

但是如果我写

ghci> permutations [1,0,0]

现在它会返回

[[1,0,0],[0,1,0],[0,0,1],[0,0,1],[0,1,0],[1,0,0]]

...这非常令人失望。由于存在三个元素，其中两个出现两次，因此人们希望只有 6!/2! = 3种排列，即

[[1,0,0],[0,1,0],[0,0,1]]

而不是通过将列表中的每个元素视为不同的元素来生成六个元素。

1) 为什么 Haskell 以上述方式实现“排列”(即将列表中的所有元素视为不同的？)

2)是否有任何标准库函数可以以“真正”的排列方式计算列表的排列？

Answer 1

记住排列具有类型

permutations :: [a] -> [[a]]

这意味着它满足自由定理

permutations . map f = (map . map) f . permutations

对于所有函数f。由于您可以任意更改参数列表的元素而不影响结果列表的结构，因此排列实际上必须是索引上的函数原始列表，而不是元素。

因此，permutations 真正要做的——它必须做的——是计算参数列表的索引的所有排列，然后应用其中的每一个排列排列列表并返回结果。 (即，

permutations xn = (map . map) (xn!!) (permutations [0..length xn - 1])

对于有限的xn)。

数学附录:

自从

xn = map (xn!!) (zipWith const [0..] xn)

对于所有 xn，任何具有排列类型的函数都必须满足

permutations xn
  = permutations (map (xn!!) (zipWith const [0..] xn)
  = (map . map) (xn!!) (permutations (zipWith const [0..] xn))

通过上面的xn方程和排列的自由定理。因此，任何具有排列类型的函数都必须仅对输入列表[1]的索引进行操作。

[1] 从技术上讲，您可以通过使用 seq 来违反此规定。但仅适用于包含 undefined 作为元素的输入列表，这在您的情况下是不正确的。