Haskell实现"zip"奇怪的错误

Question

我在haskell中有以下zip函数的实现

myzip (a:b) (z:g)
    | b == [] = []
    | g == [] = []
    | otherwise = (a,z) : myzip b g

当我将它加载到ghci中时，我得到以下错误

No instance for (Eq b)
  arising from a use of `=='
In the expression: g == []
In a stmt of a pattern guard for
               an equation for `myzip':
  g == []
In an equation for `myzip':
    myzip (a : b) (z : g)
      | b == [] = []
      | g == [] = []
      | otherwise = (a, z) : myzip b g

Failed, modules loaded: none.

我真的不知道为什么这不起作用。有人能帮我吗?

Answer 1

实际上你在问题中给出的函数编译得很好。你将得到你所引用的错误，如果你有，而不是:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:b) (z:g)
    | b == [] = []
    | g == [] = []
    | otherwise = (a, z) : myzip b g

具有显式类型签名，表明myzip适用于任意类型a和b的列表。但是你用的是b == []和g == []。相等运算符不是在任何类型上定义的，只在Eq类型类的成员类型上定义，因此您编写的代码与您给出的类型不匹配。

这是非常直接的错误信息，但是如果你刚刚学习并且还没有达到键入类的程度，那么它就有点不清楚了。

如果您更改myzip的类型签名，说明a和b需要成为Eq类型类的成员，那么您给出的代码将有效:

myzip :: (Eq a, Eq b) => [a] -> [b] -> [(a, b)]

或者如果您完全关闭类型签名(就像您在问题中所做的那样)，GHC实际上根据您使用==操作符的事实推断出该类型，并且代码只是按原样编译。

然而，检查列表是否为空可以不使用==操作符，所以你可以写myzip，这样它就可以对任何类型a和b进行操作。一种方法是使用null函数:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:b) (z:g)
    | null b = []
    | null g = []
    | otherwise = (a, z) : myzip b g

但更常见的方法是简单地使用多个方程来定义myzip，基本情况与模式[]匹配，主情况可以假设列表非空:

myzip :: [a] -> [b] -> [(a, b)]
myzip (a:[]) _ = []
myzip _ (z:[]) = []
myzip (a:b) (z:g) = (a, z) : myzip b g

请注意，这种风格也明显地表明在您的实现中存在错误。你扔掉了最后一个a或z，当列表完全为空时，没有任何情况!

当你的方程说myzip (a:b) (z:g)和然后检查b和g对空列表，它实际上是检查错误的东西太迟了。您不需要检查b是否为[]，您需要检查整个列表是否为空。但你已经假设它不是空的，并把它分解成a:b。这将导致您的代码(a)返回错误的结果，因为它丢弃了应该压缩的最后一对元素;(b)当其中一个参数是空列表时产生错误。

列表上的递归通常是这样的:

myzip :: [a] -> [b] -> [(a, b)]
myzip [] _ = []
myzip _ [] = []
myzip (a:b) (z:g) = (a, z) : myzip b g