为什么在两个相似的函数定义中类型推断与 as-pattern 不同？

Question

我有以下两个相似的函数定义：

left f (Left x) = Left (f x)
left _ (Right x) = Right x

left' f (Left x) = Left (f x)
left' _ r@(Right _) = r

当我检查这两个函数的类型签名时，我被以下类型搞糊涂了：

ghci> :t left
left :: (t -> a) -> Either t b -> Either a b
ghci> :t left'
left' :: (a -> a) -> Either a b -> Either a b

我想left和left'应该是相同的类型签名，但是haskell的类型推断给了我一个惊喜。

我不明白为什么 left 和 left' 的类型签名不同。谁能给我一些信息？谢谢！

Answer 1

在left'的第二行：

left' _ r@(Right _) = r
--      ^^^^^^^^^^^   ^

由于您使用 as 模式，因此您需要输入类型等于 return 类型，因为很明显它们是完全相同的值。 left' 的类型被限制为 a -> b -> b.

形式的东西

此限制然后向后传播以反过来限制函数的类型——希望你能看到如何；不是太难。

然而，在left的第二行，你构造了一个新值

left _ (Right x) = Right x
--                 ^^^^^^^

这个新值的类型没有被限制，所以不会出现同样的问题；它可以是 a -> b -> c 的形式，这就是您想要的。

因此，left'的类型比left的类型更受限制，这就是导致它们类型不相等的原因。

为了更具体地说明这个概念，我将更准确地向您描述这个限制是如何向后传播的。

我们知道left'的签名是(a -> b) -> Either a q -> Either b q的形式。但是，第 2 行指示 Either a q = Either b q，这意味着 a = b，因此类型现在变为 (a -> a) -> Either a q -> Either a q.

Answer 2

这里的问题是有一些 "hidden" 类型会有所不同。类型推断引擎可以推断出第一种情况，但不能推断出第二种情况。

当我们使用

Right :: forall a b. b -> Either a b

我们实际上需要选择a和b是什么类型。幸运的是，类型推断在大多数情况下为我们做出了这种选择。类型 b 很容易选择：它是 Right 的参数内部值的类型。输入 a 可以是任何东西——推理引擎必须依赖上下文来 "force" 选择 a。例如，请注意所有这些类型检查：

test0 :: Either Int Bool
test0 = Right True

test1 :: Either String Bool
test1 = Right True

test2 :: Either [(Char, Int)] Bool
test2 = Right True

现在，在你的第一个函数中

left :: (t -> a) -> Either t b -> Either a b
left f (Left x) = Left (f x)
left _ (Right x) = Right x

第一个匹配的 Right x 实际上是 Right x :: Either t b，其中隐式类型参数被选择为 t 和 b。这使得 x 具有类型 b。使用此信息，类型推断会尝试确定第二个 Right x 的类型。在那里，它可以看到它应该是 Either ?? b 的形式，因为 x :: b，但是，正如我们上面的 test 示例所发生的那样，我们可以为 ?? 使用任何东西。因此类型推理引擎选择另一个类型变量 a（一个类型可能是 t，但也可能是其他类型）。

相反，在第二个函数中

left' :: (t -> t) -> Either t b -> Either t b
left' f (Left x) = Left (f x)
left' _ r@(Right _) = r

我们为 Right _ 模式命名 (r)。如上所述，推断其具有 Either t b 类型。但是，现在我们在 = 的右边使用名称 r，因此类型推断不必在那里推断任何东西，并且可以（事实上，必须) 只需重用它已经为 r 推断出的类型。这使得输出类型与输入类型相同 Either t b，进而强制 f 为 t -> t.

类型

如果这令人困惑，您可以尝试完全避免类型推断并使用语法 Right @T @U 为类型提供显式选择以选择函数 U -> Either T U。（不过，您需要为此打开 ScopedTypeVariables、TypeApplications 扩展。）那么我们可以这样写：

left :: forall t a b. (t -> a) -> Either t b -> Either a b
left f (Left x) = Left @a @b (f x)
left _ (Right x) = Right @a @b x
                      -- ^^ -- we don't have to pick @t here!

我们也可以

left :: forall t b. (t -> t) -> Either t b -> Either t b
left f (Left x) = Left @t @b (f x)
left _ (Right x) = Right @t @b x

而且它会工作得很好。 GHC 更喜欢第一种类型，因为它更通用，允许 a 是任何类型（包括 t，但也包括其他类型）。

第二个定义中没有要指定的类型应用程序，因为它在右侧和左侧重用了相同的值 r：

left' :: forall t b. (t -> t) -> Either t b -> Either t b
left' f (Left x) = Left @t @b (f x)
left' _ r@(Right x) = r
                   -- ^^ -- can't pick @a here! it's the same as on the LHS

为什么在两个相似的函数定义中类型推断与 as-pattern 不同？

Why the difference in type-inference over the as-pattern in two similar function definitions?

haskell

type-signature