参数多态性和高级类型有什么区别？

Question

我很确定它们不一样。但是，我被 "Rust 不支持"高级类型(HKT)的常见概念，但 而是提供参数多态性。我试图解决这个问题并理解它们之间的区别，但越来越纠结。

据我了解，Rust中有更高级的类型，至少是基础类型。使用"*"表示法，HKT确实具有一种例如* -> *. 例如，Maybe是* -> *的，可以在 Haskell 中像这样实现。

data Maybe a = Just a | Nothing

这里

• Maybe是类型构造函数，需要应用于具体类型 成为一种具体的"*"。
• Just a和Nothing是数据构造函数。

在关于哈斯克尔的教科书中，这经常被用作高等类型的示例。但是，在 Rust 中，它可以简单地实现为枚举，毕竟枚举是sum 类型：

enum Maybe<T> {
Just(T),
Nothing,
}

区别在哪里？据我了解，这是一个 高等类型的完美例子。

1. 如果在Haskell中，这被用作HKT的教科书示例，为什么 说 Rust 没有 HKT？Maybe枚举不符合 香港电讯？
2. 应该说 Rust 并不完全支持 HKT 吗？
3. HKT和参数多态性之间的根本区别是什么？

在查看函数时，这种混乱仍在继续，我可以写一个参数 需要Maybe的函数，并且据我理解，HKT是一个函数 论点。

fn do_something<T>(input: Maybe<T>) {
// implementation
}

同样，在哈斯克尔，这将是类似的

do_something :: Maybe a -> ()
do_something :: Maybe a -> ()
do_something _ = ()

这就引出了第四个问题。

4. 对更高级类型的支持究竟在哪里结束？什么是 使 Rust 的类型系统无法表达 HKT 的最小示例？

相关问题：

我经历了很多与该主题相关的问题(包括他们链接到博客文章等)，但我找不到我的主要问题的答案(1 和 2)。

1. 在哈斯克尔，"高等类型"是*真的*类型吗？或者它们只是表示*具体*类型的集合，仅此而已？
2. 不带类型参数的泛型类型的泛型结构
3. 斯卡拉高等种类
4. 哪些类型的问题有助于"高等多态性"更好地解决？
5. Haskell中的抽象数据类型与参数多态性

更新

感谢您提供许多很好的答案，这些答案都非常详细并且有很大帮助。我决定接受安德烈亚斯·罗斯伯格的回答，因为他的解释对我走上正轨的帮助最大。尤其是关于术语的部分。

我真的陷入了认为每一种* -> * ... -> *都是高级的循环中。强调* -> * -> *和(* -> *) -> *之间区别的解释对我来说至关重要。

Answer 1

一些术语：

• 这种*有时被称为地面。您可以将其视为 0 阶。
任何
• 具有至少一个箭头* -> * -> ... -> *的形式都是一阶的。
• 高阶类型是具有"左侧嵌套箭头"的类型，例如(* -> *) -> *。

顺序本质上是箭头左侧嵌套的深度，例如，(* -> *) -> *是二阶的，((* -> *) -> *) -> *是三阶的，等等(FWIW，同样的概念也适用于类型本身：二阶函数是类型具有例如形式(A -> B) -> C的函数。

非地面类型(> 0阶)也称为类型构造函数(一些文献仅将地面类型称为"类型")。高级类型(构造函数)是其类型是高阶类型(> 1阶)。

因此，高级类型是采用非地面类型参数的类型。这将需要非地面类型的类型变量，而许多语言都不支持这些类型变量。哈斯克尔的例子：

type Ground = Int
type FirstOrder a = Maybe a  -- a is ground
type SecondOrder c = c Int   -- c is a first-order constructor
type ThirdOrder c = c Maybe  -- c is second-order

后两者是高级的。

同样，高级多态性描述了(参数化)多态值的存在，这些值抽象到非地面类型上。同样，很少有语言支持这一点。例：

f : forall c. c Int -> c Int  -- c is a constructor

Rust 支持参数化多态性"而不是"高级类型的说法是没有意义的。两者都是参数化的不同维度，相辅相成。当你把两者结合起来时，你就有了更高的多态性。

Answer 2

Rust 不能做的一个简单的例子是 Haskell 的Functor类。

class Functor f where
fmap :: (a -> b) -> f a -> f b
-- a couple examples:
instance Functor Maybe where
-- fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing  = Nothing
fmap f (Just x) = Just (f x)
instance Functor [] where
-- fmap :: (a -> b) -> [a] -> [b]
fmap _ []     = []
fmap f (x:xs) = f x : fmap f xs

请注意，实例是在类型构造函数、Maybe或[]上定义的，而不是完全应用的类型Maybe a或[a]。

这不仅仅是一个客厅的把戏。 它与参数多态性有很强的相互作用。由于类型变量a和类型变量fmap中的b不受类定义的约束，因此Functor实例无法基于它们更改其行为。在推理类型代码方面，这是一个非常强大的属性，也是 Haskell 类型系统的优势来自哪里。

它还有一个属性 - 您可以在高级类型变量中编写抽象的代码。 下面是几个示例：

focusFirst :: Functor f => (a -> f b) -> (a, c) -> f (b, c)
focusFirst f (a, c) = fmap (x -> (x, c)) (f a)
focusSecond :: Functor f => (a -> f b) -> (c, a) -> f (c, b)
focusSecond f (c, a) = fmap (x -> (c, x)) (f a)

我承认，这些类型开始看起来像抽象的废话。但是，当您有几个利用高级抽象的助手时，它们变得非常实用。

newtype Identity a = Identity { runIdentity :: a }
instance Functor Identity where
-- fmap :: (a -> b) -> Identity a -> Identity b
fmap f (Identity x) = Identity (f x)
newtype Const c b = Const { getConst :: c }
instance Functor (Const c) where
-- fmap :: (a -> b) -> Const c a -> Const c b
fmap _ (Const c) = Const c
set :: ((a -> Identity b) -> s -> Identity t) -> b -> s -> t
set f b s = runIdentity (f (_ -> Identity b) s)
get :: ((a -> Const a b) -> s -> Const a t) -> s -> a
get f s = getConst (f (x -> Const x) s)

(如果我在那里犯了任何错误，有人可以修复它们吗？ 我将在没有编译器的情况下从内存重新实现lens的最基本起点。

函数focusFirst和focusSecond可以作为第一个参数传递给get或set，因为它们类型中的类型变量f可以与get和set中更具体的类型统一。能够在高级类型变量上抽象f允许特定形状的函数既可以用作任意数据类型中的 setter 也可以用作 getter。 这是促成lens库的两个核心见解之一。 没有这种抽象，它就不可能存在。

(就其价值而言，另一个关键见解是，将镜头定义为这样的功能允许镜头的组成成为简单的功能组合。

所以不，它不仅仅是能够接受类型变量。重要的部分是能够使用与类型构造函数对应的类型变量，而不是一些具体的(如果未知的)类型。

Answer 3

我要恢复它：高级类型只是一个类型级别的高阶函数。

但请花一分钟时间：

考虑monad变压器：

newtype StateT s m a :: * -> (* -> *) -> * -> *

这里

- s is the desired type of the state
- m is a functor, another monad that StateT will wrap
- a is the return type of an expression of type StateT s m

什么是高等类型？

m :: (* -> *)

因为*取一种类型并返回一种类型*。

它就像类型上的函数，即类型的类型构造函数

* -> *

在像Java这样的语言中，你不能这样做

class ClassExample<T, a> {
T<a> function()
}

在Haskell中，T会有种类*->*，但是Java类型(即.class)不能有那种类型参数，即更高种类的类型。

另外，如果你不知道，在基本的Haskell中，表达式必须具有具有*的类型，即"具体类型"。任何其他类型的，如* -> *.

例如，不能创建类型Maybe的表达式。它必须是应用于参数的类型，如Maybe Int、Maybe String等。换句话说，完全应用的类型构造函数。

Answer 4

参数多态性仅指函数在其定义中不能使用类型(或种类)的任何特定特征的属性; 它是一个完整的黑盒。标准示例是length :: [a] -> Int，它仅适用于列表的结构，而不适用于存储在列表中的特定值。

HKT的标准例子是Functor类，其中fmap :: (a -> b) -> f a -> f b。不像length，a有善良的*，f有善良的* -> *。fmap还表现出参数多态性，因为fmap在其定义中不能使用a或b的任何属性。

fmap也表现出临时多态性，因为定义可以针对定义它的特定类型构造函数f进行定制。也就是说，f ~ []、f ~ Maybe等对fmap有单独的定义。不同之处在于f被"声明"为类型类定义的一部分，而不仅仅是fmap定义的一部分。(实际上，添加类型类是为了支持某种程度的临时多态性。没有类型类，则仅存在参数化多态性。可以编写支持一种具体类型或任何具体类型的函数，但不能编写介于两者之间的一些较小集合的函数。