list - 模式匹配如何与列表一起使用

Question

我刚开始学习 haskell 和模式匹配。我只是不明白它是如何实现的，[] 和 (x:_) 是否评估为不同的类型，并且由于多态性而识别此模式的函数实现，或者我只是错了，并且使用了另一种技术。

head' :: [a] -> a  
head' [] = error "Can't call head on an empty list, dummy!"  
head' (x:_) = x 

或者让我们考虑这个模式匹配函数:

tell :: (Show a) => [a] -> String  
tell [] = "The list is empty"  
tell (x:[]) = "The list has one element: " ++ show x  
tell (x:y:[]) = "The list has two elements: " ++ show x ++ " and " ++ show y  
tell (x:y:_) = "This list is long. The first two elements are: " ++ show x ++ " and " ++ show y 

我想我错了，因为每个包含不同数量元素的列表不能有不同的类型。你能解释一下 haskell 如何知道哪种模式对于某些函数实现是正确的吗？我理解它在逻辑上是如何工作的，但并不深入。请给我解释一下。

Answer 1

Haskell 的语法和运行时的实现之间存在一定程度的间接关系。您在大多数源代码中看到的列表语法实际上是一种相当常规的数据类型的糖分。下面两行是等价的:

data List a = Nil | Cons a (List a)
data [a] = [] | a : [a]  -- pseudocode

因此，当您输入 [a,b,c] 时，这会转换为内部表示形式 (a : (b : (c : []))) .

您将在顶层绑定(bind)中看到的模式匹配也是一些语法糖(没有一些次要细节)，用于将数据类型解构到模式匹配案例右侧的 case 语句。 _ 符号是通配符模式的内置符号，它匹配任何表达式(只要模式类型正确)但会向 RHS 范围添加一个变量。

head :: [a] -> a
head x = case x of
  (a : _) -> a

I think I wrong because each list with different number of elements can't have deferent type. Can you explain me how haskell knows which pattern is correct for some function implementation?

所以要回答你的问题 [] 和 (x:_) 都是同一类型(即 [a] 或 List a 在我们上面的例子中)。列表数据类型也是递归的，因此 a 类型的 Cons'ing 值的所有递归组合都具有相同的类型，即 [a]。

当编译器对 case 语句进行类型检查时，它会沿着每个 LHS 列运行，并确保所有类型都是等效的，或者可以使用称为统一的过程使其等效。在案例的右侧进行相同的操作。

Haskell“知道”哪个模式是正确的，方法是按顺序尝试每个分支并解包匹配值以查看它是否具有与模式相同数量的 cons 元素，然后继续进行正确的分支，或者模式匹配失败如果不匹配则出错。相同的过程适用于数据类型的任何模式匹配，而不仅仅是列表。