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

Question

当我问到foldl类型时,我看到的是:

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

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

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

而且,奖金问题,如果我必须定义foldl自己,我会从基础案例开始

foldl f b [] = []

但是如果基本案例采用一个列表,那么接受一个列表是没有意义的Foldable.什么是我可以用作基本案例的"空可折叠"？

Answer 1

Foldable被称为"类型类"的东西.说Foldable t =>声明t必须实现的要求Foldable.但是,t仍然存在t,并且不会Foldable像Java中那样折叠成对接口的引用.这就是你不能拥有的原因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 2

我喜欢其他答案,这些答案简要讨论了类型和类之间的区别,因此以这种方式回答问题的前半部分.为了完成这个答案,我将非常简短地重申一下; 但是请看其他答案以获得更长的解释,因为我想把大部分时间花在问题的后半部分.

所以:Foldable是一个类型类(一组类型).将t在类型foldl护林员在类型,而不是类型的集合,这解释了为什么它不能被替换Foldable.

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

如果我必须定义foldl自己,我将从基本案例开始

foldl f b [] = []

但是如果基本案例采用一个列表,那么接受一个列表是没有意义的Foldable.

如果你要定义foldl你自己,你会被创建的实例Foldable为特定类型.因为在实例中您知道涉及哪种特定类型,所以您可以为该类型编写基本案例,而无需了解其他任何实例Foldable.在Foldable列表的实例中:

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

...是完美的打字,因为我们知道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.Sets的内容,并且不能与其他Foldable实例一起使用.