为什么foldr有一个'b'类型的变量？
为什么foldr有一个'b'类型的变量？
既然Monoid是封闭的（a -> a -> a），那么我们如何在其中获得第二个类型'b'呢？我觉得foldr太宽松了，也就是说，我可以使用一个不封闭的函数进行折叠。你也会注意到fold和foldMap只有'a'。
以下是Foldable类型类的代码片段：
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 (+)是一个Monoid
foldr (++) "" ["ab", " cd"] // ok (++)是String的一个Monoid
foldr (:) [] [1,2,3] // (:) :: a -> [a] -> [a]不是一个Monoid...
我认为Foldable应该/可以只使用一个Monoid进行折叠，这个说法是错误的吗？（例如：在我看来，reduce使用的是一个可交换的Monoid，而fold使用的是一个简单的Monoid...（参见Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?））
为什么foldr有一个'b'类型的变量？
在讨论这个问题之前，我们先来看一个具体的例子，我们只考虑列表作为具体的情况。可以通过考虑单子来理解为什么'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有任何条件来成为一个单子。
通过一些例子进行更低层次的解释：
例如，注意到对于任何list :: [a]，都有foldr (:) [] list = list。为了得到上述结果，我们需要选择
b ~ [a]
。如果我们只能选择
b ~ a
，我们就无法进行类型检查。
再举一个例子，考虑any :: (a -> Bool) -> [a] -> Bool，上面的代码中，
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成为一个良好的类型。
总之，foldr在'b'上没有任何限制的另一个理由是，Endo b不需要对b有任何条件来成为一个单子。
为什么foldr有一个'b'类型变量？
在上述内容中，我们可以看到foldr的类型与foldMap的类型是一样的，只是参数的顺序有些不同。当且仅当b->b是一个幺半群时，foldr的类型与foldMap的类型是一样的。幺半群指的是从一个类型到自身的函数，可以通过函数组合进行关联。事实上，它们确实构成了一个幺半群。
什么是从一个类型到自身的函数构成幺半群？
简单来说，任意两个从一个类型到自身的函数都可以进行组合，而函数组合是关联的（(f . g) . h == f . (g . h)）。这意味着存在一个特殊的函数id，满足id . f == f == f . id；事实上，id x = x就是这个函数。这就是全部内容，信不信由你。
实际上，(:) :: a -> [a] -> [a]就是一种a -> b -> b的函数；所以，对于one :: Int ; one = 1，我们有(one 🙂 :: [Int] -> [Int]，它也是一种b -> b的函数。另外，(one +) :: Int -> Int也是一种更具体的b -> b的函数。
实际上，为了给这种类型提供Monoid实例，必须使用newtype。这基本上意味着，在阅读代码时，可以将Endo / appEndo视为语法噪声。
所以，foldr'实际上就是foldMap，只是进行了一些newtype标记（使用Endo）和取消标记（使用appEndo）：
Sum 1 <> Sum 2 = Sum (1 + 2)
Endo (1:) <> Endo (2:) = Endo ((1:) . (2:))
foldMap Sum [1,2,3] = Sum (1 + 2 + 3)
foldMap (Endo . (:)) [1,2,3] = Endo ((1:) . (2:) . (3:))
foldr' (:) [1,2,3] [4,5] = appEndo (foldMap (Endo . (:)) [1,2,3]) [4,5]
= appEndo (Endo ((1:) . (2:) . (3:))) [4,5]
= ((1:) . (2:) . (3:)) [4,5]
= [1,2,3,4,5]
foldr (:) [4,5] [1,2,3]
请注意，在(1 + 2 + 3)和((1:) . (2:) . (3:))中没有内部括号。<>（在这里是+和.）的关联性意味着实际的括号化在语义上并不重要，只有在操作上才重要。这正是重点，因为将计算分组成树状结构可以并行计算。
当然，使用foldr / Endo的实际顺序是线性的：
foldr (:) [] [1,2,3,4]
=
1 : (2 : (3 : (4 : [] )))
最后，关于(Endo #. f)中的#.是什么意思？
实际上，这是一个newtype的技巧。可以将其视为编译时的标记，运行时消失。但是，编写Sum . (1+)会隐藏它的临时性质，这可能导致非常低效的代码。也就是说，这些内容是为编译器而不是语言本身设计的。从语言的角度来看，#.就是.。#.常常在这种情况下使用。
希望这些解答能对你有所帮助！