list - Haskell - 一个非常简单的函数

Question

我正在尝试理解以下函数:

q1 :: [Int]  -> Int
q1 []                    = 0
q1 [x]                   = x
q1 (x:_:xs)              = max x (q1 xs)

当输入:q1 (map abs [-1,-6,-5,7]) 时，它得到 5。有人可以告诉我为什么会发生这种情况吗？我了解 map 的功能，但模式匹配 (x:_xs) 有点令人困惑。谢谢!

Answer 1

Haskell 中的列表是——至少在概念上——一个链表。有两种可能性:

• 一个空列表[]；或
• 一个“cons”(x:xs)，其中 x 是head(第一项)，xs tail(列表的其余部分)。

Haskell 还使用语法糖。例如 [1] 在幕后翻译成 (1:[])，而 [1,4,2,5] 到(1:(4:(2:(5:[]))))。

为什么这很重要？我们首先将尝试理解 q1 函数。如果我们查看类型，我们会看到 q1 将 Int 列表作为输入，并返回一个 Int。它被递归定义为:

q1 :: [Int]  -> Int
q1 [] = 0
q1 [x] = x
q1 (x:_:xs) = max x (q1 xs)

这意味着空列表的 q1 为零 (0)；具有一个元素 x 的列表的 q1 是 x。对于具有两个 或更多元素的列表，该列表的第一项的最大值 x 和尾部的尾部 该列表。这是因为我们使用 (x:_:xs) 进行模式匹配，它是 (x:(_:xs)) 的缩写。下划线基本上表示“不关心”。所以列表应该是一个cons，尾部也是一个cons，我们对列表的头部x感兴趣，并且列表尾部 xs 的尾部。

如果我们对此进行推理，我们就会发现 q1 返回 奇数索引 处元素的最大值(所以第一个，第三、第五等元素)。如果列表的长度为偶数，我们还用零计算最大值(因此如果奇数索引处的所有元素均为负数，函数将返回零，但这仅 em> 如果我们有一个 偶数 长度的列表)。

现在如果我们用 q1 (map abs [-1,-6,-5,7]) 调用它，这意味着我们将调用 q1 map abs 在 [-1, -6, -5, 7] 上的结果。 map abs 构造一个列表，其中 abs 应用于列表的所有元素(尽管它是延迟应用的)。所以在 map abs [-1, -6, -5, 7] 之后，我们获得了列表 [1, 6, 5, 7]。现在奇数索引处的元素是 1 和 5。所以 q1 将计算这些元素的最大值和零(因为列表的长度是四，这是偶数)。 max(0, 1, 5) 是 5。

就我个人而言，尤其是我们也考虑零但仅在列表具有偶数长度的情况下，这一事实非常“不稳定”。它可能导致难以理解的错误，因为它可能是功能细节的结果。例如，无论列表的长度如何，我们都可以用零计算最大值:

q2 :: (Num a, Ord a) => [a] -> a
q2 [] = 0
q2 [x] = max 0 x
q2 (x:_:xs) = max x (q2 xs)

或者我们可以决定根本不使用零，并且不在空列表上定义最大值，例如:

q3 :: Ord a => [a] -> a
q3 [x] = x
q3 [x,_] = x
q3 (x:_:xs) = max x (q3 xs)