参数多态性和更高种类的类型之间有什么区别？

Question

我很确定它们不一样。然而，我被 "Rust does not support" 高等类型 (HKT) 的普遍观念，但是而是提供 参数多态性 。我试图弄清楚这些并理解它们之间的区别，但越来越纠结。

据我了解，在 Rust 中有个更高级的类型，至少是基础。使用“*”符号，HKT 确实有一种例如* -> *。例如，Maybe 属于 * -> * 类型，可以在 Haskell.

中这样实现

data Maybe a = Just a | Nothing

这里，

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

在关于Haskell的教科书中，这经常被用作更高种类的例子。然而，在 Rust 中，它可以简单地实现为枚举，毕竟它是一个 sum 类型 :

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

哪里不一样了？据我了解，这是一个高等类型的完美典范。

如果在Haskell中将其用作HKTs的教科书示例，为什么说 Rust 没有 HKT？ Maybe 枚举不符合香港时间？
是否应该说 Rust 不完全支持 HKT？
HKT 和参数多态性之间的根本区别是什么？

在查看函数时，这种困惑仍在继续，我可以编写一个参数化的采用 Maybe 的函数，据我所知，HKT 是一个函数参数。

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

同样，在 Haskell 中会是这样的

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

这就引出了第四个问题。

对更高种类类型的支持到底在哪里结束？什么是使 Rust 的类型系统无法表达 HKT 的最小示例？

更新

感谢您提供的许多很好的答案，这些答案都非常详细并且帮助很大。我决定接受 Andreas Rossberg 的回答，因为他的解释最能帮助我走上正轨。特别是关于术语的部分。

我真的陷入了这样一种循环，即所有种类 * -> * ... -> * 都是 更高种类的 。强调 * -> * -> * 和 (* -> *) -> * 之间差异的解释对我来说至关重要。

Answer 1

我要恢复它了：更高种类的类型只是类型级别的高阶函数。

但请稍等一下：

考虑 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 :: (* -> *)

因为取一种类型 * 和 returns 取一种类型 *.

它就像一个类型上的函数，也就是一个类型构造函数

* -> *

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

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

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

此外，如果您不知道，在基本 Haskell 中，表达式必须具有类型 *，即 "concrete type"。任何其他类型，例如 * -> *.

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

Answer 2

Rust 不能做的一个简单例子是 Haskell 的 Functor class.

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]。

这不仅仅是一个客厅把戏。它与参数多态性有很强的相互作用。由于类型 fmap 中的类型变量 a 和 b 不受 class 定义的约束，因此 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

一些术语：

种类*有时被称为ground。您可以将其视为第 0 阶。
任何一种形式 * -> * -> ... -> * 至少有一个箭头是一阶。
高阶种类是具有"nested arrow on the left"的种类，例如(* -> *) -> *.

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

非ground kind类型（order > 0）也称为type constructors（有些文献仅将ground kind类型称为"types"）。更高种类的类型（构造函数）是其种类为高阶（阶 > 1）的类型。

因此，更高种类的类型是采用非基本种类参数的类型。这将需要非地面种类的类型变量，许多语言都不支持。 Haskell中的示例：

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

后两者比较高等

同样，higher-kinded 多态性 描述了（参数化的）多态值的存在，这些值对非基本类型进行抽象。同样，很少有语言支持这一点。示例：

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

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

Answer 4

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

HKT 的标准示例是 Functor class，其中 fmap :: (a -> b) -> f a -> f b。与 length 不同，a 具有种类 *，f 具有种类 * -> *。 fmap 也表现出参数多态性，因为fmap不能使用a或b中的任何属性它的定义。

fmap 也表现出特别的多态性，因为定义可以定制为特定的类型构造函数 f 为其定义。即f ~ []、f ~ Maybe等分别定义了fmap，区别在于f是"declared"类型[=]的一部分48=] 定义，而不仅仅是 fmap 定义的一部分。（实际上，添加了 typeclasses 以支持某种程度的临时多态性。如果没有 typeclasses，only 参数多态性存在。您可以编写一个函数支持 one 具体类型或 any 具体类型，但不支持介于两者之间的一些较小的集合。）

参数多态性和更高种类的类型之间有什么区别？

What's the difference between parametric polymorphism and higher-kinded types?

haskell

type-theory

higher-kinded-types

rust

parametric-polymorphism

相关问题：

更新