模式匹配函数列表时没有 (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 的实例）。您可能认为这是无稽之谈，因为您是在与空列表进行比较，所以元素的值无关紧要。但是typewise，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 实际上是为所有可折叠对象定义的，但出于我们的目的，您可以将其视为列表函数）

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

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

但是，您过早地停止了递归一步。您可以将函数列表与 [] 直接匹配作为基本情况，在这种情况下，值列表是 return 值。

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

按照chepner的建议，我把原来的代码重写成了一个fold。

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

我确实想知道是否有比颠倒论点更优雅的方法来做到这一点，但是 foldl 的签名迫使我动手。

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

No instance of (Eq ([a] -> [a])) when pattern matching a list of functions

haskell

equals

instance