为什么foldr有'b'型变量？

Question

由于Monoid是关闭的(a - > a - > a),我们怎样才能获得第二种类型'b'？我的印象是折叠太过宽松,在某种意义上我可以使用折叠功能而不是关闭.您还会注意到fold和foldMap只有'a'.

下面是可折叠类型类的片段:

class Foldable t where
    fold :: Monoid m => t m -> m
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b

例如:

foldr (+) 0 [1..5] // ok (+) is a monoid
foldr (++) "" ["ab", " cd"] // ok (++) is a monoid for String
foldr (:) [] [1,2,3] // (:) :: a -> [a] -> [a] is not a monoid...

我在想一个Foldable应该/只能用一个monoid折叠,这个说法是错的吗？(例如:在我的脑海里,就像reduce使用一个可交换的monoid并折叠一个简单的monoid ...(请参阅函数式编程中的reduce和foldLeft/fold之间的区别(特别是Scala和Scala API)？))

Answer 1

我只会将列表视为具体案例.

理解为什么b不受约束的一种方法是考虑幺半群:

newtype Endo b = Endo { appEndo :: b -> b }

instance Monoid (Endo b) where
   mempty = Endo id
   mappend (Endo f) (Endo g) = Endo (f . g)

注意,这是由形式的函数形成b -> b的幺半群,其中幺半群操作是合成,而中性元素是同一性函数.

至关重要的是,无论是什么,这都是幺半群b!

然后,直到同构,我们可以写

foldr :: (a -> Endo b) -> b -> [a] -> b
foldr e n list = appEndo (mconcat (map e list)) n

所以大多数工作都是在Endo幺半群中完成的.

重新排序论点,我们甚至得到了

foldr :: (a -> Endo b) -> [a] -> b -> b

甚至,直到同构,

foldr :: (a -> Endo b) -> [a] -> Endo b
foldr e = mconcat . map e 

(这是通常的实现方式foldMap.)

因此,b不受限制的另一个理由foldr是,Endo b不需要任何条件b成为幺半群.

通过一些例子进行更多低级别的解释:

作为一个例子,请注意foldr (:) [] list = list任何list :: [a].

要获得上述内容,我们需要选择b ~ [a].如果我们只能选择b ~ a我们无法打字检查上面的例子.

另一个例子,考虑一下

any :: (a -> Bool) -> [a] -> Bool
any p = foldr (\x acc -> p x || acc) True

以上x :: a和acc :: b ~ Bool,通常是不同类型的.

另外,不要忘记foldr列表的定义:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c n [] = n
foldr c n (x:xs) = c x (foldr c n xs)

在这里,没有必要b进行foldr良好的打字.