Haskell中的多态性

Question

我刚接触 Haskell 并正在阅读《Haskell基础教程》。

顺便说一下，这个问题是普遍的问题，与这本书无关，我选取此问题只是为了举例说明。

在第10章第10.5节Q5的f部分中：

以下都是非常类似于你已经看到的简单折叠，但每个都至少有一个错误。请修复它们并在 REPL 中进行测试。

f) foldr const 'a' [1..5]

它会出现以下错误：

无法处理由字面量“1”引起的 Num Char 实例

简单地说，这里不能使用 1 作为 Char。

但我在这一章节中读到，Fold 就像文本重写器，用函数替换 cons(:)，用累加器替换空列表。因此结果就是（我缩短了列表）：

foldr const 'a' [1..2] 
to 
(1 `const` (2 `const` 'a')) 

它在工作中没有编译器错误。

那么出了什么问题呢？ 为什么第一个不起作用，而重写后的代码可以？

但我发现在重写的表单中，const 有两种形式。

Int -> Int -> Int 
and 
Int -> Char -> Int

可能是由于这个原因，我把const的类型修复成了这样。

cont :: Int -> Int -> Int
cont = const

现在当我开始使用它时

(1 `cont` (2 `cont` 'a'))

Couldn't match expected type `Int' with actual type `Char'

似乎当我们在使用Haskell的多态函数时，无法将其用于其他形式。也许应该将列表折叠描述为以下内容：折叠就像文本重写器，将cons（：）替换为函数，修复函数类型并将空列表替换为累加器。请分享您对此的看法。是否只有Haskell而其他类型的语言也有相同的行为？或者我完全错了？

- hanan

---

请勿使用图片来显示代码或错误信息。请复制并粘贴您的错误，以便让更多人能够解决您的问题。谢谢。 - user1198582

@MichaelLitchard 我已经发布了图片以及代码+错误信息的文本形式，请阅读它。 - hanan

举个简单的例子来说，这个不起作用的原因本质上与你无法编写map show ['a', 1 :: Int]相同，即使map f [a, b]=[f a, f b]且你可以编写[show 'a', show (1 :: Int)]。这是因为它们不是相同的f：show :: Char -> String和show :: Int -> String(或者使用TypeApplications，show @Char和show @Int)是不同的函数，同样的道理也适用于const @Int @Char和const @Int @Int。 - Jon Purdy

^^^这应该是被接受的答案。（抄送@JonPurdy） - Will Ness

Answer 1

在表达式中：

(1 `const` (2 `const` 'a')) 
   ---A---    ---B---

我们使用多态函数const两次。每次使用都会实例化多态函数类型，以满足所有类型检查所需的类型。 const的通用类型为:

const :: a -> b -> a

假设数字字面量的类型为Int，以便简化说明。 当我们写2 `const` 'a'（上图中的点--B--），Haskell理解上面的类型变量a必须是Int，而b必须是Char，因此这里我们正在使用

const :: Int -> Char -> Int

因此，2 `const` 'a'的结果是Int类型。

了解了这个之后，我们现在可以意识到，在上面的--A--点使用的const仅在我们选择类型变量a和b都为Int时才能进行类型检查。因此，我们正在使用。

const :: Int -> Int -> Int

由于类型系统允许在每个函数使用点处都有一个独特的多态类型实例化，因此这是可能的。

---

值得注意的是，该表达式

(\c -> 1 `c` (2 `c` 'a')) const

beta-reduce是一个表达式，它可以简化（技术上: beta-reduces）成原始表达式，但是它是不可类型化的。在这里，const只使用一次，因此它的类型只能被实例化一次，但是没有单个类型实例可以用于两个点c。这是类型推断引擎的已知限制，在执行Hindley-Milner推断的所有函数语言中共享。

您使用的foldr const ....也存在同样的问题。

一开始可能会感到困惑，因为我们可能有两个表达式，其中一个简化成另一个，但只有其中一个是可类型化的。然而，这是生活的事实。从理论上讲，Haskell满足以下“主题约简”属性:

• 如果表达式e1被打了类型，并且e1约简成表达式e2，那么表达式e2就被打了类型。

然而，Haskell（像大多数语言一样）无法满足以下“主题扩展”属性:

• 如果表达式e2被打了类型，并且e1约简成表达式e2，那么表达式e1就被打了类型。

因此，尽管已经不可能使一个打了类型的表达式约简成一个未打类型的表达式，但却可以使一个未打类型的表达式约简成一个打了类型的表达式。你发现的一个例子就是这样。更简单的一个例子是(\x -> True) ("ill-typed" "term")，它是无法打类型的（它使用一个字符串作为函数），但简化为True，这是打了类型的。

- chi

---

实际上，这为我们提供了另一个 if 的替代方案：foldr const z xs == if null xs then z else head xs。 :) - Will Ness

Answer 2

你的分析是正确的，虽然有点太详细了。如果你愿意，你可以从稍微高一些的层面来看待这个问题。

foldr :: (a -> r -> r) -> r -> [a] -> r
const :: b -> c -> b

（如果我选择的类型变量与您习惯的不同，请谅解 - alpha等价性表示变量名称无关紧要，并且保持名称不同可以更容易地看出正在发生什么。）

如果您使用这些类型并统一它们使foldr const正常工作，您会得到类似于以下的东西：

(a -> r -> r) ~ (b -> c -> b)
a ~ b (first arg)
r ~ c (second arg)
r ~ b (result)
r ~ a (by transitivity)

foldr const :: a -> [a] -> a (substitution)

其中 ~ 表示 "这些类型是相同的"。

因此，仅从 foldr 和 const 就可以看出列表元素的类型必须与另一个参数的类型一致。

不过，你说得对，如果在类型检查之前完全内联 foldr，则生成的表达式将成功检查。但这是一个不太充分的情况。如果你执行 foldr const 'a' [] 呢？由于它会被简化为 'a'，所以它也能通过类型检查 - 但如果传递给它的列表非空，则其类型与之不同。

这正是 Haskell 类型系统旨在防止的问题。表达式的类型应完全由其子表达式的类型推导而来。值永远不应该(*)被考虑，因此无论子表达式是空列表还是非空列表，表达式都需要具有相同的结果类型。

(*)好吧，GHC 支持比 Haskell 2010 更多的功能。像 GADTs 这样的扩展可以启用一种依赖于值的类型，但只能以维护更大的一致性属性的非常特定的方式进行。

- Carl

Answer 3

我认为，这样更简单，而且const函数不符合foldr预期的签名：

Prelude> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
Prelude> :t const
const :: a -> b -> a

所以Haskell尝试将a和b都泛化（通过确定它们都有足够的类型类），最终发现1是一个数字，但'c'没有实现这个类型类。

- madbird

Answer 4

那么出了什么问题呢？为什么第一个函数不起作用，而重写后的函数却可以工作？

这是一个有趣的问题，我觉得值得解释一下。

首先，foldr 的例子不能工作，因为编译器告诉你，类型不匹配。当限制在列表上时，foldr 有以下类型，我将以一种与你尝试给它的参数相匹配的方式来写：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr    const           'a'   [1..2]

从中我们可以看到，类型变量 a 和 b 必须取特定的值 - a 必须是一个数字（你可以将其视为仅为 Int，尽管它实际上具有“多态数字”类型 Num a => a，即它可以是任何数字类型），而 b 必须是 char。因此，只有当 const 可以具有如下类型时才能正常工作。

Int -> Char -> Char

或者将Int替换为任何数值类型也可实现相同的功能。

但是你选择哪种数值类型并不重要，除非（正如编译器指出的那样），你以某种方式为Char定义了一个Num实例。这是因为const具有类型。

a -> b -> a

为了与上述内容相匹配，a 和 b 必须都是 Char，这意味着数字类型（我假设为 Int 以简化问题）必须是 Char。由于该类型不是字符类型（但在理论上可以成为一个字符类型，尽管这不是个明智的想法），所以编译器错误信息现在应该是有意义的。

那么为什么你引用的“笨拙”的形式：

(1 `const` (2 `const` 'a')) 

工作？如果编译成功，那么上面的foldr将等同于这个。但是，当foldr无法编译时，并不意味着上面的代码也会失败。它之所以起作用是因为const是一个多态函数 - 它可以适用于任何两个参数，任何类型，并返回第一个参数。因此，它逐渐缩小到（我简化了使用Int表示任何数字类型）：

1 `const` 2

使用 const :: Int -> Char -> Int。

1

（使用const :: Int -> Int -> Int）

请注意，const的两个调用实际上具有2种不同的类型。这是可以的，因为const是多态的。但是，将const传递到foldr中并期望每次在foldr内部调用时具有不同的类型是不好的。

这不是任何一种通用规则，至少如果您使用RankNTypes语言扩展。使用该扩展，您可以定义接受多态函数作为参数然后使用不同的类型应用它的函数：

example :: (forall a. a -> a) -> (Int, Bool)
example f = (f 1, f True)

但是，上面显示的foldr的签名与此完全不同。虽然其类型签名中的a和b可以自由变化，但由于您传递了一个数字列表，a被强制为数字类型，而由于累加器'a'，b被强制为Char - 因此唯一可能起作用的“版本”const是Int -> Char -> Char类型的（再次为简单起见特殊化数字类型），这不是const的可能类型。

- Robin Zigmond