Haskell中如何让both函数支持异构对？

问题背景 #

以下Haskell代码可以正常运行：

> bimap succ succ (1, 'a')
(2, 'b')

但定义both后调用会触发类型错误：

> both f = bimap f f
> both succ (1, 'a')

<interactive>:11:12: error:
    • No instance for (Num Char) arising from the literal ‘1’
    • In the expression: 1
      In the second argument of ‘both’, namely ‘(1, 'a')’
      In the expression: both succ (1, 'a')

原因很明确：第一种场景中，多态函数succ会被分别推导为(Enum b, Num b) => b -> b和Char -> Char两个不同的类型实例；但both的定义要求传入的f必须是单一类型的函数，两次调用必须使用同一个类型版本的succ，因此触发类型冲突。

核心问题 #

让both函数支持异构对（即处理(a,b)类型的输入，返回(a',b')且a'与b'类型不同）是否完全不可能？如果是，原因是什么？或者只需编写正确的类型签名就能实现？

尝试的方案及问题 #

我尝试了如下类型签名的代码，它可以编译通过：

both :: forall (f :: * -> *) a b. (forall c. f c -> f c) -> (a, b) -> (f a, f b)
both f (a, b) = (f undefined, f undefined)

但将undefined替换为实际的a和b时，会出现类型不匹配错误：

<interactive>:3:20: error:
    • Couldn't match expected type ‘f a’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
        the type signature for:
          both :: forall (f :: * -> *) a b.
                  (forall c. f c -> f c) -> (a, b) -> (f a, f b)
        at <interactive>:2:1-80
    • In the first argument of ‘f’, namely ‘a’
      In the expression: f a
      In the expression: (f a, f b)
    • Relevant bindings include
        a :: a (bound at <interactive>:3:9)
        f :: forall c. f c -> f c (bound at <interactive>:3:6)
        both :: (forall c. f c -> f c) -> (a, b) -> (f a, f b)
          (bound at <interactive>:3:1)

<interactive>:3:25: error:
    • Couldn't match expected type ‘f b’ with actual type ‘b’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          both :: forall (f :: * -> *) a b.
                  (forall c. f c -> f c) -> (a, b) -> (f a, f b)
        at <interactive>:2:1-80
    • In the first argument of ‘f’, namely ‘b’
      In the expression: f b
      In the expression: (f a, f b)
    • Relevant bindings include
        b :: b (bound at <interactive>:3:12)
        f :: forall c. f c -> f c (bound at <interactive>:3:6)
        both :: (forall c. f c -> f c) -> (a, b) -> (f a, f b)
          (bound at <interactive>:3:1)

解答 #

可行性结论 #

不是完全不可能，但需要利用Rank-N类型来突破普通多态的限制，直接通过普通类型签名无法实现。

原因分析 #

1. 普通多态的限制：原both f = bimap f f的问题在于，Haskell的参数化多态要求f必须被实例化为单一类型的函数（比如c -> c），无法让f在两次调用中使用不同的类型实例。

2. 你尝试的类型签名方向错误：(forall c. f c -> f c)要求f的参数是f c类型，但你的输入是a和b（并非f a或f b），因此类型不匹配是必然结果。

正确实现方式 #

通过Rank-N类型允许f是一个多态函数，能分别适配a和b的类型：

{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE FlexibleContexts #-}

-- 适配带Enum约束的多态函数（比如succ）
both :: (forall c. Enum c => c -> c) -> (a, b) -> (a, b)
both f (x, y) = (f x, f y)

此时调用both succ (1, 'a')就能正常得到(2, 'b')，因为succ满足forall c. Enum c => c -> c的约束，会被分别实例化为Num和Char版本。

如果需要更通用的、支持任意多态函数的版本，可以去掉约束，但这类签名只能接受真正全多态的函数（比如恒等函数）：

{-# LANGUAGE RankNTypes #-}

both :: (forall c. c -> c) -> (a, b) -> (a, b)
both f (x, y) = (f x, f y)

总结 #

• 要让both支持异构对，必须使用Rank-N类型让传入的f成为多态函数，而非单一类型的函数。
• 你之前的尝试错误在于混淆了f的作用对象类型，导致输入的a/b无法匹配f的参数要求。

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