参数多态与高等级类型有什么区别？

Question

我很确定他们不一样.然而,我被"Rust不支持"高级类型(HKT)的常见概念所困扰,而是提供参数多态性.我试图了解这一点并理解它们之间的区别,但却变得越来越纠结.

根据我的理解,Rust中有更高级的类型,至少是基础知识.使用"*" - 符号,HKT确实有一种例如* -> *.例如,Maybe是善良的* -> *,可以在Haskell中像这样实现.

data Maybe a = Just a | Nothing

这里,

• Maybe 是一个类型构造函数,需要应用于具体类型才能成为类型"*"的具体类型.
• Just a并且Nothing是数据构造函数.

在关于Haskell的教科书中,这通常被用作高级类型的示例.但是,在Rust中它可以简单地实现为枚举,毕竟它是一个和类型:

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

区别在哪里？据我所知,这是一个更好的类型的完美的例子.

1. 如果在Haskell中这被用作HKT的教科书示例,为什么说Rust没有HKT？不将Maybe枚举资格作为一个HKT？
2. 是否应该说Rust不完全支持HKT？
3. HKT和参数多态之间的根本区别是什么？

在查看函数时,这种混淆仍在继续,我可以编写一个参数函数,它Maybe可以将HKT作为函数参数.

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

再次,在Haskell中会是这样的

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

这导致了第四个问题.

4. 对高等级类型的支持到底在哪里？什么是使Rust的类型系统无法表达HKT的最小例子？

相关问题:

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

1. 在Haskell中,"更高级的类型"*真的*类型？或者他们只是表示*具体*类型的集合,仅此而已？
2. 没有类型参数的泛型类型的通用结构
3. Scala中更高的键控类型
4. 什么类型的问题有助于"更高通道的多态性"更好地解决？
5. 抽象数据类型与Haskell中的参数多态性

更新

感谢您提供了许多非常详细且有很多帮助的好答案.我决定接受Andreas Rossberg的回答,因为他的解释帮助我走上了正确的轨道.特别是关于术语的部分.

我真的陷入了这样一种思维的循环:一切* -> * ... -> *都是高级的.这强调的区别的解释* -> * -> *和(* -> *) -> *是至关重要的我.

Answer 1

一些术语:

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

的顺序基本上是箭头的左侧嵌套,例如深度,(* -> *) -> *是二阶,((* -> *) -> *) -> *是三阶等(FWIW,相同的概念适用于类型本身:第二次函数是其类型具有例如形式(A -> B) -> C.)

非地类的类型(order> 0)也称为类型构造函数(有些文献仅将地类的类型称为"类型").较高级的类型(构造函数)是其类型为高阶(order> 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

后两者是较高的.

同样,更高通道的多态性描述了(参数化)多态值的存在,这些值抽象了非基础类型.同样,很少有语言支持这一点.例:

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和b类型fmap不受类定义的约束,因此实例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

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

香港电讯的标准例子是Functor班级,其中fmap :: (a -> b) -> f a -> f b.不像length,哪里a有种类*,f有种类* -> *.fmap 也显示出参数多态,因为fmap不能使用的任何任何财产a或b在它的定义.

fmap也表现出ad hoc多态性,因为定义可以定制f为定义它的特定类型构造函数.也就是说,fmapfor f ~ [],f ~ Maybe等有不同的定义.不同之处在于,它f被"声明"为类型类定义的一部分,而不仅仅是定义的一部分fmap.(实际上,添加了类型类以支持某种程度的特殊多态性.没有类型类,只存在参数多态.您可以编写一个支持一种具体类型或任何具体类型的函数,但不能支持一些较小的集合.)

Answer 4

我要恢复它:一个更高级的类型只是一个类型级的高阶函数.

但是花点时间:

考虑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类型(即类)不能具有这种类型的类型参数,即更高级的类型.

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

例如,您无法创建类型的表达式Maybe.它被应用到的参数等类型的Maybe Int,Maybe String等等.换言之,完全应用类型构造函数.