为什么 foldr 有一个 'b' 类型的变量？
Why does foldr have a 'b' type variable?
由于 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 (+) is a monoid
foldr (++) "" ["ab", " cd"] // ok (++) is a monoid for String
foldr (:) [] [1,2,3] // (:) :: a -> [a] -> [a] is not a monoid...
我在想 Foldable should/could 只能用幺半群折叠，这个说法错了吗？ （例如：在我的脑海中，reduce 就像是在使用一个可交换的幺半群并折叠一个简单的幺半群。（参见 Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?））
我只会将列表视为具体案例。
理解为什么 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 类型正确。
查看您引用的 Foldable class 定义，foldr 的类型只是对其参数进行了重新排序，
foldr' :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b) ,
实际上统一与
的类型（变得相同）
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m ,
provided b -> b是一个monoid,(b -> b) ~ Monoid m => m即Monoid (b -> b)的类型所谓的内函数（即从一个类型到同一类型的函数），正如您所期望的那样，它们与函数组合相关联。
它们确实形成了一个幺半群。
什么意思，内函数在函数组合下形成幺半群 ((f . g) x = f (g x))？简单地说，任何两个内函数都可以组合，函数组合是关联（(f . g) . h == f . (g . h) - 你可以自己检查一下使用它的定义）。也意味着存在特殊函数id使得id . f == f == f . id；确实 id x = x 符合要求。信不信由你。
的确是(:) :: a -> [a] -> [a]（读作：(:)有类型a -> [a] -> [a]），是a -> b -> b的一种；因此，对于 one :: Int ; one = 1 我们有 (one :) :: [Int] -> [Int] 这也是一种 b -> b。
还有 (one +) :: Int -> Int，这是一种更特殊的 b -> b，但仍然如此。
作为技术细节，必须使用 newtype 来实际为该类型提供其 Monoid 实例。这基本上意味着，在阅读代码时，您可以将 Endo / appEndo 视为语法噪音。
所以 foldr' 确实是 foldMap，直到一些新类型标记（使用 Endo）和取消标记（使用 appEndo）：appEndo (Endo f) == f，那是全部：
Sum 1 <> Sum 2 = Sum (1 + 2) -- Sum is a tag, saying "we want (+)"
Endo (1:) <> Endo (2:) = Endo ((1:) . (2:)) -- Endo is a tag, saying "we want (.)"
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:)) 中缺少内括号。 <>（这里是 + 和 .）的结合性意味着实际的括号在语义上无关紧要，只在操作上有关系。这就是重点，因为将计算分组为一棵树打开了并行计算的可能性：
(1 + 2 + 3 + 4 + 5 + + ...)
=
( ( (1 + 2) + (3 + 4) ) + ( ( (5 + 6) + ... ) ... ) ... )
=
......
当然 foldr / Endo 的实际顺序是线性的：
foldr (:) [] [1,2,3,4]
=
1 : (2 : (3 : (4 : [] )))
（在这里复制评论中的一些内容，正如我们应该做的那样。）
- 我发现的一个技巧可以帮助我理解错综复杂的新类型代码：当您看到类似
Endo f <> Endo g = Endo $ x -> (f . g) x 的内容时，请将其写成 等式伪代码 ，例如 appEndo (Endo f <> Endo g) x = (f . g) x 被视为 <> 的 定义 – 它不是有效的 Haskell，但对我来说更清楚地表达了意图。 IE。我倾向于将 lambda 视为实现，将方程视为方程 (an example)（当然，"tangled" 不适用于此处，但例如，与 Continuation monad 等）
你问的是，
"what #. does in (Endo #. f)?
- 嗯，解释是here。在我们的例子中，它表示
Endo #. (:) = coerce (:) `asTypeOf` (Endo . (:))。这与写 let { g :: a -> Endo [a] ; g = coerce (:) } in g 相同。 Endo b 实际上与 b -> b 相同，只是标签 Endo 允许我们为其定义 Monoid 实例。 instance Monoid (b->b) where .... 无效 Haskell。所以我们可以将 Endo #. (:) 读作 Endo . (:)。
- 这与
newtype是什么有关。它可以看作是编译时标签。它在 运行 时消失。 （例如，Sum 2 在 运行 时实际上只是 2，而 Product 2 也只是 2。但是写作 Sum . (1+) 隐藏了其短暂的性质，即 apparently "can lead to very inefficient code"。 IOW 这些东西是针对编译器的，而不是针对语言本身的。在语言方面，#. 只是 .。 #通常用于这种情况。
由于 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 (+) is a monoid
foldr (++) "" ["ab", " cd"] // ok (++) is a monoid for String
foldr (:) [] [1,2,3] // (:) :: a -> [a] -> [a] is not a monoid...
我在想 Foldable should/could 只能用幺半群折叠，这个说法错了吗？ （例如：在我的脑海中，reduce 就像是在使用一个可交换的幺半群并折叠一个简单的幺半群。（参见 Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?））
我只会将列表视为具体案例。
理解为什么 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 类型正确。
查看您引用的 Foldable class 定义，foldr 的类型只是对其参数进行了重新排序，
foldr' :: Foldable t => (a -> (b -> b)) -> t a -> (b -> b) ,
实际上统一与
的类型（变得相同） foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m ,
provided b -> b是一个monoid,(b -> b) ~ Monoid m => m即Monoid (b -> b)的类型所谓的内函数（即从一个类型到同一类型的函数），正如您所期望的那样，它们与函数组合相关联。
它们确实形成了一个幺半群。
什么意思，内函数在函数组合下形成幺半群 ((f . g) x = f (g x))？简单地说，任何两个内函数都可以组合，函数组合是关联（(f . g) . h == f . (g . h) - 你可以自己检查一下使用它的定义）。也意味着存在特殊函数id使得id . f == f == f . id；确实 id x = x 符合要求。信不信由你。
的确是(:) :: a -> [a] -> [a]（读作：(:)有类型a -> [a] -> [a]），是a -> b -> b的一种；因此，对于 one :: Int ; one = 1 我们有 (one :) :: [Int] -> [Int] 这也是一种 b -> b。
还有 (one +) :: Int -> Int，这是一种更特殊的 b -> b，但仍然如此。
作为技术细节，必须使用 newtype 来实际为该类型提供其 Monoid 实例。这基本上意味着，在阅读代码时，您可以将 Endo / appEndo 视为语法噪音。
所以 foldr' 确实是 foldMap，直到一些新类型标记（使用 Endo）和取消标记（使用 appEndo）：appEndo (Endo f) == f，那是全部：
Sum 1 <> Sum 2 = Sum (1 + 2) -- Sum is a tag, saying "we want (+)"
Endo (1:) <> Endo (2:) = Endo ((1:) . (2:)) -- Endo is a tag, saying "we want (.)"
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:)) 中缺少内括号。 <>（这里是 + 和 .）的结合性意味着实际的括号在语义上无关紧要，只在操作上有关系。这就是重点，因为将计算分组为一棵树打开了并行计算的可能性：
(1 + 2 + 3 + 4 + 5 + + ...)
=
( ( (1 + 2) + (3 + 4) ) + ( ( (5 + 6) + ... ) ... ) ... )
=
......
当然 foldr / Endo 的实际顺序是线性的：
foldr (:) [] [1,2,3,4]
=
1 : (2 : (3 : (4 : [] )))
（在这里复制评论中的一些内容，正如我们应该做的那样。）
- 我发现的一个技巧可以帮助我理解错综复杂的新类型代码：当您看到类似
Endo f <> Endo g = Endo $ x -> (f . g) x的内容时，请将其写成 等式伪代码 ，例如appEndo (Endo f <> Endo g) x = (f . g) x被视为<>的 定义 – 它不是有效的 Haskell，但对我来说更清楚地表达了意图。 IE。我倾向于将 lambda 视为实现，将方程视为方程 (an example)（当然，"tangled" 不适用于此处，但例如，与 Continuation monad 等）
你问的是，
"what
#.does in(Endo #. f)?
- 嗯，解释是here。在我们的例子中，它表示
Endo #. (:) = coerce (:) `asTypeOf` (Endo . (:))。这与写let { g :: a -> Endo [a] ; g = coerce (:) } in g相同。Endo b实际上与b -> b相同，只是标签Endo允许我们为其定义 Monoid 实例。instance Monoid (b->b) where ....无效 Haskell。所以我们可以将Endo #. (:)读作Endo . (:)。 - 这与
newtype是什么有关。它可以看作是编译时标签。它在 运行 时消失。 （例如，Sum 2在 运行 时实际上只是2，而Product 2也只是2。但是写作Sum . (1+)隐藏了其短暂的性质，即 apparently "can lead to very inefficient code"。 IOW 这些东西是针对编译器的，而不是针对语言本身的。在语言方面，#.只是.。#通常用于这种情况。