为什么使用 `join` 的函数组合可以改变函数输入？

Question

我最近开始学习 Haskell，我正在尝试进行以下函数组合 (join . mapM)，但是从这个函数中得到了一些我不理解的奇怪类型。我认为 GHC 会假设 mapM 类型中的 t == m 和 mapM 的输出将变为 m (m b) ，这将是可连接的，或者它不会，这将由于类型不匹配而出错。相反，发生了以下情况：

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)
join :: Monad m => m (m a) -> m a
join . mapM :: Traversable t => (a -> t a -> b) -> t a -> t b

我不明白这怎么可能。按照我的理解，函数组合应该使用第一个（或第二个取决于你如何看待它）函数的输入和第二个函数的输出。但是这里 mapM 的预期输入函数从一元函数变为二元函数，我不知道为什么。即使 GHC 不能像我所做的那样假设 t == m，这是我一半预料的，它应该因为类型不匹配而出错，而不是更改输入函数类型，对吧？这里发生了什么？

Answer 1

首先你将 mapM 专精于：

mapM' :: Traversable t => (a -> x -> b) -> t a -> x -> t b

（因为 (->) x 是一个 monad）

然后您将其进一步专门化为：

mapM'' :: Traversable t => (a -> t a -> b) -> t a -> t a -> t b

（我们只是将 x 固定为 t a）

最后我们适当地专门化join：

join' :: (x -> x -> r) -> x -> r

（同样，(->) x 是一个 monad）

希望成分 join' . mapM'' 是

的原因变得更加明显

join' . mapM'' :: Traversable t => (a -> t a -> b) -> t a -> t b

Answer 2

也许以下内容会更有启发性：

flip mapT :: (Traversable t, Monad m) => t a -> (a -> m b) -> t (m b)
sequenceA :: (Traversable t, Monad m) =>                      t (m b) -> m (t b)
flip mapM :: (Traversable t, Monad m) => t a -> (a -> m b)            -> m (t b)

           flip liftM :: Monad m      => m a -> (a -> m b) -> m (m b)
 join                 :: Monad m      =>                      m (m b) -> m    b
(join .) . flip liftM :: Monad m      => m a -> (a -> m b)            -> m    b
(>>=)                 :: Monad m      => m a -> (a -> m b)            -> m    b

（在这里和那里使用一些比最通用的类型更专业的类型；还有 renamed mapT f = runIdentity . traverse (Identity . f)）。

您的具体问题不太有趣。类型推导是一个完全机械的过程。某些实体必须兼容才能使整个表达式有意义，因此它们的类型必须统一：

 (join . mapM) a_mb  x  =       -- a_mb :: a -> m b
 = join (mapM  a_mb) x
 = join   ta_mtb     x          -- ta_mtb :: t a -> m (t b)

加入一个函数就是调用它两次，

 =        ta_mtb     x  x

这意味着 x 是 t a 所以 m 是 t a ->：

        x :: t a 
 ta_mtb   :: t a -> m   (t b)
 ----------------------------
 ta_mtb x ::        m   (t b)
          ~       t a -> t b
          x ::    t a 
 ----------------------------
 ta_mtb x x ::           t b

因此a_mb :: a -> m b ~ a -> t a -> b.

为什么使用 `join` 的函数组合可以改变函数输入？

Why can function composition with `join` change function inputs?

haskell

monads

function-composition