haskell - 为什么文件夹具有“b”类型变量？

由于Monoid是封闭的（a-> a-> a），我们如何才能获得第二种类型'b'？我觉得印象文件夹太宽容了，从某种意义上说，我可以使用一个未关闭的函数来折叠它。您还会注意到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应该/只能与一个monoid折叠，这是错误的说法吗？ （例如：在我的脑海中，reduce就像在使用可交换的monoid并折叠一个简单的monoid。（请参见Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?））

最佳答案

查看您引用的Foldable类定义，foldr的类型及其参数重新排序，

    foldr' ::   Foldable t =>     (a -> (b -> b)) -> t a -> (b -> b)   ,

实际上与（的类型）统一为

    foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m          ,

提供的b -> b是一个单义词(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，但对我来说，表达意图更加清晰。即我倾向于将lambda视为实现，方程式也是如此，方程式（an example）（“纠结”当然不适用于此处，但例如适用于Continuation monad等）。


你在问


“ #.在(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“这可能导致效率很低的代码”。 IOW这个东西是给编译器的，不是给语言本身的。在语言方面，#.只是.。 #通常在这种情况下使用。