类型构造函数可以被视为函数式编程语言中的类型吗?

Can type constructors be considered as types in functional programming languages?

我正在学习 Haskell 编程语言,我有 Scala 和 Java 开发人员的背景。

我正在阅读类型构造函数背后的理论,但我无法理解它们是否可以被视为类型。我的意思是,在 Scala 中,您使用关键字 classtrait 来定义类型构造函数。想想List[T],或者Option[T]。同样在 Haskell 中,您使用相同的关键字 data,用于定义新类型。

那么,类型构造函数也是类型吗?

好吧,类型和类型构造函数有它们自己的演算,它们都有种类。例如,如果你在 ghci 中使用 :k (Maybe Int),你会得到 *,现在这是一个正确的类型并且它(通常)有居民.在这种情况下 NothingJust 42 等。* 现在有一个更具描述性的别名 Type

现在你可以看看Maybe的那种构造函数,:k Maybe会给你* -> *。使用别名,这是 Type -> Type,这是您所期望的。它需要一个Type构造一个Type。现在,如果您将类型视为一组值,那么一个很好的问题是 Maybe 有哪些值组?好吧,none 因为它不是真正的类型。您可能会尝试 Just 之类的东西,但它的类型 a -> Maybe a 类型 Type,而不是类型 Maybe 类型 Type -> Type.

我们来看一个类比:函数。在一些数学分支中,函数被称为值构造函数,因为它们就是这样做的:你输入一个或多个值,然后它们从这些值构造一个新值。

类型构造器与类型构造器完全相同,只是在类型级别上不同:您放入一个或多个类型,然后它们从这些类型构造一个新类型。从某种意义上说,它们是类型级别的函数。

现在,我们的类比:你问的问题的类比是什么?嗯,就是这样:"Can value constructors (i.e. functions) be considered as values in functional programming languages?"

答案是:这取决于编程语言。现在,对于函数式编程语言,几乎所有(如果不是全部)答案都是 "Yes"。这取决于您对 "functional programming language" 的定义。有些人将函数式编程语言定义为以函数作为值的编程语言,因此根据定义,答案很简单 "Yes" 。但是,有些人将函数式编程语言定义为不允许副作用的编程语言,在这样的语言中,函数不一定是值。

最著名的例子可能是 John Backus 的 FP,来自他的开创性论文 编程能否摆脱冯诺依曼风格? – 函数式风格及其程序代数。在 FP 中,有 "function-like" 事物的层次结构。函数只能处理值,函数本身不是值。然而,有一个概念"functionals"是"function constructors",即它们可以将函数(以及值)作为输入and/or产生函数作为输出,但它们不能将泛函作为输入and/or 将它们作为输出。

因此,FP 可以说是一种函数式编程语言,但它没有函数作为值。

注意:作为值的函数也称为 "first-class functions",将函数作为输入或 return 作为输出的函数称为 "higher-order functions"。

如果我们看一些类型:

1   :: Int
[1] :: List Int
add :: Int → Int
map :: (a → b, List a) → b

你可以看到我们可以很容易地说:任何类型中有箭头的值都是函数。任何类型中包含多个箭头的值都是高阶函数。

同样,这同样适用于类型构造函数,因为除了类型级别之外,它们实际上是相同的东西。在某些语言中,类型构造函数可以是类型,而在某些语言中则不能。例如,在 Java 和 C♯ 中,类型构造函数不是类型。例如,在 C♯ 中不能有 List<List>。您可以 写下 Java 中的类型 List<List>,但这是误导,因为两个 List 表示不同的东西:第一个 List是类型构造函数,第二个List原始类型,所以这实际上是不是使用类型构造函数作为一种类型。

上面的类型示例等同于什么?

Int     :: Type
List    :: Type ⇒ Type
→       :: (Type, Type) ⇒ Type
Functor :: (Type ⇒ Type) ⇒ Type

(注意,我们怎么总是有 Type?事实上,我们只处理类型,所以我们通常不写 Type 而是简单地写 *,发音"Type"):

Int     :: *
List    :: * ⇒ *
→       :: (*, *) ⇒ *
Functor :: (* ⇒ *) ⇒ *

所以,Int 是一个正确的类型,List 是一个接受一种类型并产生一个类型的类型构造函数,(函数类型构造函数)接受两种类型并且returns 是一种类型(假设只有一元函数,例如使用柯里化或传递元组),Functor 是类型构造函数,它本身采用类型构造函数,returns 是一种类型。

论文"type-types"被称为种类。与函数一样,任何带箭头的东西都是类型构造函数,任何超过一个箭头的东西都是 higher-kinded 类型构造函数.

和函数一样,有些语言允许更高种类的类型构造函数,有些则不允许。你在问题中提到的两种语言,Scala和Haskell,但是如上所述,Java和C♯不做

但是,当我们查看您的问题时,情况变得复杂了:

So, are type constructors also types?

不是,不是。至少不是我所知道的任何语言。看,虽然你可以有更高种类的类型构造函数,这些构造函数将类型构造函数作为输入 and/or return 它们作为输出,但你不能拥有具有类型构造函数的表达式、值、变量或参数作为它的类型。您不能拥有接受 List 或 return 的函数 List。您不能有 Monad 类型的变量。但是,你 可以 有一个 Int.

类型的变量

所以,很明显,类型和类型构造函数之间存在差异。

至少在Haskell中,有一个层次,大致可以这样描述

是在运行时间存在的东西,值如1'a'(+),例如。

每个术语都有一个类型,例如IntCharInt -> Int -> Int

每种类型都有一个种类,所有类型都有相同的种类,即*

[] 这样的类型构造函数具有种类 * -> *,因此它不是类型。相反,它是从一种类型到另一种类型的映射


还有其他类型,包括(除了 ** -> *,每个都有一个例子):

  • * -> * -> * (Either)
  • (* -> *) -> * -> *ReaderT,一个 monad 转换器)
  • Constraint (Num Int)
  • * -> Constraint(Num;这是一种类型class)