haskell - 为什么foldr有一个 'b'类型的变量？

Question

既然幺半群是封闭的(a -> a -> a)，我们如何才能得到第二种类型“b”？我的印象是foldr 太宽松了，因为我可以使用未关闭的折叠功能。您还会注意到，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...

我在想可折叠应该/只能用幺半群折叠，这个说法是错误的吗？ (例如:在我看来，reduce 就是使用可交换幺半群并折叠一个简单的幺半群..(参见 Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)? ))

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类型良好。