当模式匹配函数列表时，没有 (Eq ([a] -> [a])) 的实例

Question

考虑以下代码：

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss
  | (fs == []) = yss
  | otherwise = step fs yss
  where yss = map f xss

它抛出以下错误：

No instance for (Eq ([a] -> [a])) arising from a use of ‘==’
  (maybe you haven't applied a function to enough arguments?)

  |
3 |   | (fs == []) = res
  |      ^^^^^^^^

fs

应该是 要么是函数列表，要么是空列表，那么为什么编译器要尝试从中创建一个函数呢？

Answer 1

仅当可以检查列表元素是否相等时（

Eq

的实例），您才能检查列表是否相等。您可能认为这是无稽之谈，因为您正在与空列表进行比较，因此元素的值并不重要。但从类型上来说，Haskell 将所有这些列表视为只是列表，并且不知道它是否为空，因此它不能让比较发生。

幸运的是，有一个专门用于此目的的函数：

null :: [a] -> Bool

，它检查列表是否为空：

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss
  | null fs = yss
  | otherwise = step fs yss
  where yss = map f xss

（免责声明：

null

实际上是为所有可折叠项定义的，但出于我们的目的，您可以将其视为列表函数）

您还可以使用模式防护进行模式匹配（因为模式匹配可以识别空列表）：

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss
  | [] <- fs = yss
  | otherwise = step fs yss
  where yss = map f xss

Answer 2

除了Aplet123的答案之外，您还可以使用模式匹配直接匹配空列表（因为

[]

是数据构造函数）：

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step (f:fs) xss = case fs of
                    [] -> yss
                    otherwise -> step fs yss
     where yss = map f xss

但是，您太早停止了递归一步。您可以将函数列表与

[]

直接匹配作为基本情况，在这种情况下，值列表就是返回值。

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step [] xss = xss
step (f:fs) xss = step fs (map f xss)
-- step [] = id
-- step (f:fs) = step fs . map f

此时，您可能想探索使用折叠代替显式递归。

Answer 3

根据切普纳的建议，我已将原始代码重写为折叠。

step :: [[a] -> [a]] -> [[a]] -> [[a]]
step cs xss = foldl rmap xss cs
  where rmap xs f = map f xs

我确实想知道是否有比颠倒论证更优雅的方法，但是

foldl

的签名迫使我采取行动。