我不确定我是否理解 haskell 中 foldl 函数的类型定义

Question

当我询问foldl类型时，我看到的是：

*Main> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

在这种情况下，t a是什么？

我想这意味着该函数正在使用 Foldable 参数化 a 但我什至不确定语法。例如，为什么我不能用 Foldable a 替换 t a？

而且，奖金问题，如果我必须自己定义 foldl，我会从基本情况开始

foldl f b [] = []

但是如果基本情况采用列表，那么接受 Foldable 就没有多大意义了。我可以用作基本案例的 "empty Foldable" 是什么？

Answer 1

在上下文 (Foldable t) => ... 中 t 是可折叠类型。例如，列表类型 [].

foldl 的一些更具体的类型是

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> Tree a -> b

Foldable t => ... 可以理解为 t 必须是 Foldable。不是类型构造函数Foldable应用到类型t！因此 Foldable t 甚至不是一种类型，您永远不能在 =>.

的右侧使用它

Answer 2

Foldable 是一个叫做 "typeclass" 的东西。说 Foldable t => 声明 t 必须执行 Foldable 的要求。但是，t 仍然是 t，并且不会像在 Java 中那样折叠成对 Foldable 接口的引用。这就是为什么你不能只有 Foldable a.

一定要查看 https://hackage.haskell.org/package/base-4.10.1.0/docs/Data-Foldable.html 以获得对 Foldable 要求的解释以及适合您的方法。

无论如何，如果您想使用 Foldable 的方法之一，则可以使用已知的 Foldable 类型，例如 Set:

import qualified Data.Set as S
import Data.Foldable

sumSet :: (Num n) => S.Set n -> n
sumSet ns = foldl' (\ n acc -> n + acc ) 0 ns --make this pointfree if you want

或者您可以采用类型参数并将其约束为可折叠：

sumFld :: (Num n, Foldable f) => f n -> n --different signature
sumFld ns = foldl' (\ n acc -> n + acc ) 0 ns --same implementation!

以下打印 6，两次：

main :: IO ()
main = print (sumSet $ S.fromList [1, 2, 3]) >> print (sumFld $ S.fromList [1, 2, 3])

Answer 3

我喜欢其他答案，它们简要讨论了类型和类之间的区别，因此以这种方式回答了问题的前半部分。为了使这个答案完整，我将非常简短地重申这一点；但请参阅其他答案以获得更长的解释，因为我想将大部分时间花在问题的后半部分。

所以：Foldable 是一个类型类（类型的集合）。 foldl 类型中的 t 是类型的护林员，而不是类型的集合，这解释了为什么它不能被 Foldable 替换。

但我认为这也是一个其他答案没有解决的非常有趣的问题：

If I had to define foldl myself, I would start with the base case
foldl f b [] = []
But if the base case takes a list, than it would not make much sense to accept a Foldable.

如果您要自己定义 foldl，您将为 特定类型 创建 Foldable 的实例。因为在您知道涉及哪种特定类型的实例中，您可以为 that 类型编写基本案例，而无需了解 Foldable 的任何其他实例。在列表的 Foldable 实例中：

instance Foldable [] where
    foldl f b [] = b

...完全是 well-typed，因为我们知道 t ~ []。另一方面，在另一种类型的实例中，我们当然必须使用不同的基本情况。例如：

import qualified Data.Set as S
instance Foldable S.Set where
    foldl f b s | S.null s = b

同样，在 instance 块 内是可以的，因为那样我们就有了 t ~ S.Set。我们可以（并且通常必须）编写仅适用于 S.Set 且不适用于其他 Foldable 实例的东西。

Answer 4

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
In this case, what is t a?

I guess it means that the function is using a Foldable parametrized with a [...]

完全正确。但是请注意，它是“a Foldable 参数化为 a”，而不是“Foldable 参数化为 a”。正如所解释的，当你在 => 的左边写 Foldable t 时，你是在说关于类型（构造函数）t.用 Foldable a 替换 t a 有点像把形容词放在应该是名词的地方。

继续你的奖励问题：foldl 恰好是 Foldable class 的一个方法。这意味着您可以在为类型编写 Foldable 的实例时提供 foldl 的适当定义，您可以在其中使用该类型的特定功能（例如 [] 是列表的构造函数——另见 ).

如果 foldl 不是 Foldable 的方法，那么在实现 t a 参数时唯一可以用来处理它的是Foldable（foldr、foldMap 等）的（其他）方法，因为除了它具有 Foldable实例。（也许令人惊讶的是，可以以这种方式实现 foldl。这种实现作为 Foldable class 中的 foldl 方法的默认提供，因此如果您认为没有必要，您可以在编写实例时不必自己实现它。）

我不确定我是否理解 haskell 中 foldl 函数的类型定义

I'm not sure I understand the type definition of the foldl function in haskell

syntax

haskell

types

signature