haskell - Elem 如何处理单个元素

Question

问题是将列表元素的连续副本打包到子列表中。
我不明白elem在这里使用单个元素，

例如，

pack [1,1,2,2,3,4]

然后 x将为 1 和 (head (pack xs))将是 1。
怎么能:

1 `elem`  1

工作时 elem是 a -> [a] -> Bool 类型?

另外，请解释递归。

pack :: (Eq a) => [a] -> [[a]]
pack [] = []
pack [x] = [[x]]
pack (x:xs) = if x `elem` (head (pack xs))
              then (x:(head (pack xs))):(tail (pack xs))
              else [x]:(pack xs)

Answer 1

在您的示例中，x将为 1，但 head (pack xs)不是1。其实从它的类型签名可以看出pack xs的类型必须是 [[Int]] (或至少 [[a]] 对于某种数字 a )即数字列表的列表，所以 head (pack xs)有类型 [Int] ，而不是输入 Int .不管它的值是多少，它都不可能是1 .

如果还不清楚，请查看更短的示例 pack [1,2] .它将匹配模式 pack (x:xs)与 x=1和 xs=[2] ，所以 elem 的右侧电话将是 head (pack [2]) .您可以验证这是否等同于 head [[2]]计算结果为 [2] ，现在是表达式:

1 `elem` [2]

很有意义。

请记住，即使 head返回列表的第一个元素，Haskell 允许列表列表，列表列表的第一个元素是另一个列表。

编辑:为了解释递归，让我们看一个 pack [1,1,2] 的完整示例详细地。每次我们尝试评估 pack调用，我们将使用 pack 的模式之一我已经编号:

pack [] = []               -- #1
pack [x] = [[x]]           -- #2
pack (x:xs) = if x `elem` (head (pack xs))    -- #3
              then (x:(head (pack xs))):(tail (pack xs))
              else [x]:(pack xs)

当 Haskell 试图评估 pack [1,1,2] , 因为 [1,1,2]相当于 1:[1,2] (如果您不明白为什么，请查看 : 运算符的定义并尝试几个示例!)，它匹配模式 #3 和 x=1和 xs=[1,2] .因此，Haskell 可以使用模式#3 的右侧用这些替换值来评估这个 x和 xs .为了完全清楚，带有这些替换的 RHS 如下所示，我们将其称为“表达式 (A)”:

if 1 `elem` (head (pack [1,2]))
then (1:(head (pack [1,2]))):(tail (pack [1,2]))
else [1]:(pack [1,2])

在继续之前，请确保您相信这是正确的!现在，评估这个表达式最难的部分是弄清楚如何评估 pack [1,2] ，它在几个地方使用。那么，让我们弄清楚 Haskell 如何评估 pack [1,2] .再次，因为 [1,2]相当于 1:[2] (检查一下!)，这匹配模式 #3 和 x=1和 xs=[2] .具有这些替换的模式 #3 的 RHS 如下，我们将其称为“表达式 (B)”:

if 1 `elem` (head (pack [2]))
then (1:(head (pack [2]))):(tail (pack [2]))
else [1]:(pack [2])

要计算表达式 (B)，我们需要计算出 pack [2] 的值。 .这一次，这个表达式将模式 #2 与 x=2 匹配。 . (实际上，它也会匹配模式 #3，与 x=2 和 xs=[] 但 Haskell 使用第一个匹配的模式，因此它从不考虑这种可能性。)替换 x=2进入模式#2 的 RHS，我们得到 pack [2] 的以下等效值，我们将其称为“表达式 (C)”，尽管它很短，可能不值得命名。

[[2]]

把它代入上面的表达式(B)，我们得到:

if 1 `elem` (head [[2]])
then (1:(head [[2]])):(tail [[2]])
else [1]:[[2]]

我在这里所做的一切都被替换了 pack [2]与 [[2]]它出现的所有地方，然后我删除了一些没有改变含义的额外括号。 if 中的条件语句与 1 `elem` [2] 相同, 为假，所以值为 [1]:[[2]]可以改写为 [[1],[2]] . (再次，检查您是否不明白为什么。)这就是表达式 (B) 的最终值，因此是 pack [1,2] 的最终值.现在，我们可以将此值代入表达式 (A) 以获得:

if 1 `elem` (head [[1],[2]])
then (1:(head [[1],[2]])):(tail [[1],[2]])
else [1]:[[1],[2]]

现在，因为 head [[1],[2]]只是 [1] ， if 中的条件声明是 1 `elem` [1]这是真的，所以 Haskell 评估 then 给出的部分条款。这很难看，但你应该能够说服自己它的值(value)是:

(1:(head [[1],[2]])):(tail [[1],[2]])
= (1:[1]):[[2]]
= [1,1]:[[2]]
= [[1,1],[2]]

这是表达式 (A) 的最终值，但当然是 pack [1,1,2] 的值。 ，所以你可以看到这一切都解决了。