5

（这是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”，就像 for 的类型一样(.)。

然后我要求ghci计算它的类型。它通过以下类型成功：

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

如何从foldMapand(.)的类型派生该类型？我特别困惑的是，在's 类型中t (t1 a)找不到的“新”类型如何出现在 for 类型中。foldMapfoldMap . foldMap

4

3 回答 3

15
于 2013-09-08T18:07:02.547 回答
2 
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m

也可以看作

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

因为->联想到右边。插入到定义中

(.) :: (y -> z) -> (x -> y) -> (x -> z)

我们明白了

x = (Monoid m) => a -> m
y = (Foldable ty, Monoid m) => ty a -> m

在这里你必须a用ty ain替换foldMap：

z = (Foldable ty, Foldable tz, Monoid m) => tz (ty a) -> m

你得到的(.)是

x -> z

这只是另一种说法

(Foldable ty, Foldable tz, Monoid m) => (a -> m) -> (tz (ty a) -> m)

其中，当不必要的括号被删除时

(Foldable ty, Foldable tz, Monoid m) => (a -> m) -> tz (ty a) -> m

或者——正如ghci它所写的——</p> 

(Foldable t, Foldable t1, Monoid m) => (a -> m) -> t (t1 a) -> m
于 2013-09-08T18:01:01.573 回答
2

Omitting the typeclass constraints for the moment, the signature for foldMap and (.) may be written:

foldMap :: (a -> m) -> (t a -> m)
    (.) :: (y -> z) -> (x -> y) -> (x -> z) -- this is just a change of variables

Here we have used the fact that function application associates to the right.

So analyzing the type signature of foldMap . foldMap sets up these correspondences:

      foldMap          .              foldMap
(a -> m) -> (t a -> m)   ( a' -> m') -> (t' a' -> m')    (a' -> m') -> (t a -> m)
  (y     ->    z)     ->        (x   ->   y)          ->     (x     ->    z)

I.e. we have the following type equalities:

y = a -> m
z = t a -> m
x = a' -> m'
y = t' a' -> m'
x = a' -> m'
z = t a -> m

which reduces to:

a = t' a'
m = m'

i.e. the type of foldMap . foldMap is (a' -> m) -> (t (t' a') -> m) or equivalently (a' -> m) -> t (t' a) -> m.

于 2013-09-08T18:11:29.747 回答