`foldMap的类型.foldMap`

Question

(这是来自Typeclassopedia的练习.)

如何计算两个非平凡函数的组合类型,如foldMap . foldMap？

对于简单的情况,这很简单:只需看看它的类型 (.)

(.) :: (b -> c) -> (a -> b) -> (a -> c)

并找到类型a,b并c为两个功能.

在这种情况下foldMap,类型是

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

我认为无法将此功能的类型"拆分"为两部分,因此我可以获得"a","b"和"c"类型(.).

然后我要求ghci计算它的类型.它成功了以下类型:

Prelude Data.Foldable> :t foldMap . foldMap 
foldMap . foldMap
  :: (Foldable t, Foldable t1, Data.Monoid.Monoid m) =>
     (a -> m) -> t (t1 a) -> m

如何从foldMap和(.)类型中推导出该类型？我特别感到困惑的是,在类型t (t1 a)中找不到的"新"类型如何foldMap显示在类型中foldMap . foldMap.

Answer 1

在简单的情况下工作的相同的等式推理技术将继续在这个更复杂的情况下工作.需要记住的一件重要事情是,这->是正确联想的; 这意味着a -> b -> c是一样的a -> (b -> c); 因此,Haskell中的所有函数只接受一个输入并产生一个输出,因此可以组合.(这种等价性是在任何地方进行部分应用的能力背后的原因.)因此,我们可以为foldMapas 重写类型签名

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

为清楚起见,我将给出两种foldMap不同名称的出现,并为其类型变量使用不同的名称; 我们会有foldMap? . foldMap?,在哪里

foldMap? :: (Foldable s, Monoid n) => (a -> n) -> (s a -> n)
foldMap? :: (Foldable t, Monoid m) => (b -> m) -> (t b -> m)
(.)      :: (d -> e) -> (c -> d) -> (c -> e)

因此,必须是这样的

foldMap? . foldMap? :: c -> e

但什么是c和e,以及有什么d,让这个工作？放弃阶级限制(他们只是在最后联合在一起,并且会在整个过程中混乱一切)​​,我们知道

                                            foldMap? . foldMap? ---+
                                                                   |
                                                                   |
       /-------foldMap?-------\    /-------foldMap?-------\    /---+--\
(.) :: (d        -> e         ) -> (c        -> d         ) -> (c -> e)
       ((b -> m) -> (t b -> m)) -> ((a -> n) -> (s a -> n))

这导致了以下等式(记住Haskell拼写类型相等~):

(c -> d) ~ ((a -> n) -> (s a -> n))
(d -> e) ~ ((b -> m) -> (t b -> m))

因为它们在函数类型上是相等的,所以我们知道域和范围分别彼此相等:

c ~ (a -> n)
e ~ (t b -> m)
d ~ (b -> m)
d ~ (s a -> n)

我们可以d通过及物性来解决这种平等性

(b -> m) ~ (s a -> n)

然后,由于双方都是函数类型,我们可以分开这个平等来得出结论

b ~ s a
m ~ n

所以d ~ (s a -> n),换句话说,只是foldMap?技巧的结果类型是b -> m,输入类型的foldMap?通用性足以与前一类型统一!(这里,统一是类型推理器所做的;当更多特定类型替换为类型变量时,两种类型可以统一,如果它们可以相同.)

最后,那么,对于代入c和e,我们得到

(c -> e) ~ ((a -> n) -> e)                 by the equality for c
         ~ ((a -> n) -> (t b -> m))        by the equality for e
         ~ ((a -> m) -> (t b -> m))        by the equality for n
         ~ ((a -> m) -> (t (s a) -> m))    by the equality for b

因此,当我们添加完整的类约束列表(记住Monoid m并且Monoid n实际上是相同的约束,因此m ~ n)并删除冗余的括号对时,我们得到

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

其中,重命名,与GHCi给你的相同.

请特别注意嵌套类型t (s a)显示的最后一步.这来自b上面的统一,在平等的内部d.我们知道结果类型foldMap? . foldMap?是t b -> m针对某些人的b; 它恰好将约束的输出foldMap?和输入统一为类型.我们总是可以用更复杂的类型表达式来统一类型变量(只要更复杂的表达式不涉及原始类型变量; 并且将无法统一),这有时会导致类似于在幕后发生的有趣类型.foldMap?bs abt bt (s a)