Haskell中`join bimap`的类型签名推导与类型转换疑问

先对两个函数的类型做变量重命名，避免推导过程中变量名冲突：

• join :: Monad m => m (m x) -> m x
• bimap :: Bifunctor p => (a -> b) -> (c -> d) -> p a c -> p b d

join bimap是函数应用，等价于把bimap作为参数传给join，因此bimap的类型必须和join的入参类型m (m x)完全匹配，推导核心是利用「函数类型(->) r本身是Monad实例」这个特性。

步骤1：对齐bimap类型与join的入参类型 #

首先将bimap的类型做柯里化展开，也就是你已经写出的形式：

bimap :: (a -> b) -> ( (c -> d) -> (p a c -> p b d) )

我们把join入参的m (m x)展开，代入m = (->) (a -> b)（也就是m是入参为a->b的函数Monad），展开后：

m (m x) = (a -> b) -> ( m x ) = (a -> b) -> ( (a -> b) -> x )

将上面两个类型做匹配，可以直接得到对应关系：

• (a -> b) -> x = (c -> d) -> (p a c -> p b d)
• 因此x = (c -> d) -> (p a c -> p b d)，m确定为(->) (a -> b)

步骤2：推导join bimap的初始返回类型 #

join的返回类型是m x，代入上面得到的m和x的匹配结果，得到初始返回类型：

m x = (a -> b) -> x = (a -> b) -> ( (c -> d) -> (p a c -> p b d) )

步骤3：利用函数Monad的join语义补充约束 #

函数Monad的join实现逻辑是将同一个入参传给两层嵌套的函数，对应实现为join f = \r -> f r r。
对应到当前场景，也就是类型为a->b的入参，会同时传给bimap的第一个和第二个参数槽位，因此必然有约束：a -> b = c -> d，可以拆解为两个等价约束：

• a = c
• b = d

步骤4：代入约束简化类型 #

将a=c、b=d代入初始返回类型：

1. 双函子的入参p a c替换为p c c
2. 双函子的返回值p b d替换为p d d
3. 两个相同的函数参数(a->b)和(c->d)合并为一层

最终得到简化后的类型：

join bimap :: Bifunctor p => (c -> d) -> p c c -> p d d

快速验证技巧 #

你可以直接把join bimap等价展开为\f -> bimap f f，语义是给双函子的两个映射位置传入同一个函数，自然要求双函子的两个类型参数初始一致、映射后也一致，和推导结果完全对应。

内容的提问来源于stack exchange，提问作者Karen Fisher