当模式与函数列表匹配时，没有 (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

根据chepner的建议，我将原始代码重写为fold。

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

我确实想知道是否有比推翻论点更优雅的方法来做到这一点，但foldl的签名迫使我不得不这么做。