haskell - Haskell 中涉及列表推导式、递归和删除函数的排列

Question

我是一名 Haskell 初学者，正在学习书中的练习。第一个问题要求我定义一个函数，从整数列表中删除第一次出现的整数。

例如

delete 5 [1,5,3,5,1]

输出:

[1,3,5,1]

第二个问题要求我创建一个函数，该函数使用我刚刚定义的删除函数，该函数将整数列表作为参数，并将所有排列的列表输出为列表。

例如

perms [1,2,3]

输出:

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

我努力尝试，放弃并用谷歌搜索解决方案。

这是我发现的:

perms [] = [[]]
perms xs = [ i:j | i <- xs, j <- perms $ delete i xs ]

我环顾四周，发现了许多其他类似的解决方案，几乎相同，只是使用不同的变量名称和括号而不是 $ 符号，所以我猜测这是惯用解决方案的常见问题.

我只是有点迷失在试图准确理解这段代码在做什么。我正在通过递归寻求一步一步的解释，以了解这段代码如何创建排列列表？

Answer 1

与任何对列表进行操作的递归函数一样，这可以分为两种情况:

1) 该函数应该对空列表执行什么操作？

2) 如果我知道该函数在长度 n 的列表上执行什么操作，我可以用它来弄清楚该函数应该在长度 n + 1 的列表上执行什么操作吗？ .

一旦你知道了这两件事，你就有了一个适用于任何列表的定义(至少一个有限长度的列表 - 对于无限长度的一个列表，这样的过程当然永远不会结束；这在这里并不重要，因为它谈论无限列表中的排列没有多大意义)。 [如果您有任何数学背景，您会认为这是 mathematical induction 定律的简单陈述。 .]

对于perms函数，很明显只有一种方法可以排列空列表的 0 个元素:另一个空列表。这给出 [[]]对于基本情况，如示例解决方案的第一行所示。

对于递归/归纳步骤，假设我们有一个列表 xs长度n (其中 n > 0 )，并假设(正如我们被允许的那样)我们已经知道如何计算任何长度 n - 1 列表的所有排列。 .

每个排列必须以 xs 的特定元素开始- 我们将此元素称为 i ，并思考如何得到 xs 的所有排列其第一个元素是 i 。应该清楚的是，这些与列表 delete i xs 的所有排列完全对应。 (即 xs 删除一个 i) - 给定排列 j后者的列表 i : j是 xs 的排列以 i 开头，相反 xs 的所有此类排列可以通过这种方式获得。

请注意，这正是列表 [ i:j | j <- perms $ delete i xs ]

(顺便注意一下，由于我们假设 i 在 xs 中， delete i xs 确实有长度 n - 1 ，所以通过归纳假设我们知道如何计算它。)

i当然是完全任意选择的 - 以及 xs 的所有元素将需要被视为某些排列的第一个元素。因此，我们只需将所有元素 i 的上述所有内容放在一起即可在xs - 这正是递归步骤中的表达式:

[ i:j | i <- xs, j <- perms $ delete i xs ]

您可能需要慢慢地阅读上面的一些内容，几次，然后才能理解 - 但它从根本上来说是非常基本的逻辑(并且像大多数基本逻辑一样，有一个令人讨厌的习惯，通常看起来比实际情况更复杂)。