Scala中的高级类型 [英] Higher Kinded Types in Scala
问题描述
我正在阅读《 Scala中的函数编程》一书，在《 Monoids》一章中，他们讨论了一个看起来像这样的Monoid接口:
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
稍后，它们通过扩展此接口来定义特定的Monoid实例.例如，
val intMonoid = new Monoid[Int] {
...
}
val listMonoid = new Monoid[List[Int]] {
...
}
在阅读本章第10章的几页后，我遇到了更高种类的类型"，根据书中的描述，更高种类的类型"本身就是可以接受其他类型的类型.
trait Foldable[F[_]] {
...
...
}
因此，根据本书的特点，可折叠性是一种更高种类的类型.我的问题是，对我而言，Monoid [A]也适合更高种类的类型"定义，因为它可以使用List [A].我的理解正确吗?如果不是，那么在Scala中如何使更高种类的类型成为更高种类的类型?
因此，一元类型构造函数接受一个参数并产生一个类型.现在，这里的情况如何?
def listMonoid[A] = new Monoid[List[A]] {
...
...
}
我的listMonoid函数是HKT吗?
一些术语:
- 正确的类型(例如Int)
- 一阶类型(例如List [_])；我们也可以说一阶种类
- 类型较高的类型(例如Monad [M [_]]
当你说
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
val listMonoid = new Monoid[List[Int]] {
def op(l: List[Int], l2: List[Int]) = List(1,2)
def zero = List(1,2)
}
您正在使用某种类型A参数化Monoid特征，它可以(如您所注意到的)是简单类型，也称为适当类型(例如Int)或参数化类型(例如List[Int])，或者甚至List[Set[Map[Int, Int]]).这使Monoid成为一阶类型.我们也可以说这是一个一元类型构造函数-它需要一种类型来产生最终类型.
与Monoid不同，某些抽象(例如Monad)需要通过类型构造函数进行参数设置. Int不再起作用.它必须是某种类型，不能产生另一种类型".由类型构造函数进行参数化的抽象(即由一阶类型"参数化)是一种更高种类的类型.这是一个示例:
trait Monad[M[_]] {
def op[A, B](m: M[A], f: A => M[B]): M[B]
def zero[A](a: A): M[A]
}
object ListMonad extends Monad[List] {
def op[A, B](m: List[A], f: A => List[B]) = m.flatMap(f)
def zero[A](a: A) = List[A](a)
}
val listMonad = ListMonad.zero(42)
val result = ListMonad.op(listMonad, (i: Int) => List(i - 1, i, i + 1))
// result = List(41, 42, 43)
因此Monad由一阶类型(一元类型构造函数)参数化，这使Monad本身成为更高种类的类型.
请注意Monad如何实际上并不在类级别上关心内部类型"本身，因为它将由方法op和zero定义.您也可以说trait Monad[M[A]]并在类ListMonad的定义点修复"类型A(例如，将其修复为Int)，但是这样就失去了灵活性(您的ListMonad将只能构造和flatMap一个List[Int]，则您需要一个不同的类，例如List[String]).
这与不是高等类型的Monoid不同；它不需要类型构造函数即可产生类型.如果需要它，那么您永远都不会有Monoid[Int]，因为Int不是类型构造函数.
还请注意我怎么说Monad需要一个 unary 类型构造函数，这意味着它仅采用一种类型(不同于Map需要两种类型).类型构造函数通常用星号和箭头表示:
- 一元一阶类型构造函数为
* -> *(它采用单个类型并产生最终类型，例如Set) - 二进制一阶类型构造函数是
* -> * -> *(二进制类型构造函数，需要两种类型来产生最终类型，例如Map) - 类型较高的一元类型是
(* -> *) -> *(采用单个一元类型构造函数来生成最终类型，例如Monad)
等
因此，一阶类型采用简单/具体/适当的类型并生成最终类型，而类型较高的类型则高于上一级.它需要一阶类型才能产生最终类型.
在编辑"部分回答您的问题:好的，我想我知道是什么让您感到困惑. listMonoid不是类型，因此它不能是类型较高的类型.这是一种方法. Monad[List[Int]]是完全解析的类型. Monad[F[A]]也已完全解决.但是，Monad本身是高阶类型.
让我对功能进行平行讨论.如果您具有函数foo(x: Int)，则诸如foo(42)或foo(someIntegerValue)之类的函数调用会产生具体值.这些类似于Monad[List[Int]]和Monad[F[A]].但是，foo本身是一个函数，就像Monad本身是类型构造函数一样.
如果foo采用简单值(不是函数)，则它是一阶函数；如果它接受或返回一个函数，则它是一个高阶函数.与类型构造函数相同.如果采用简单类型，则它是一阶类型构造函数.示例:List.如果采用其他类型构造函数，则它是高阶类型构造函数(也称为高种类型).例如:Monad.
请勿将解析的类型与类型构造函数混合使用.考虑函数foo是否是高阶的是有意义的.这取决于其参数和返回类型.但是，思考foo(42)是否为高阶是没有意义的.这不是函数，而是函数应用程序，可以产生价值. Monad[List[Int]]不是类型构造函数，而是类型构造函数List到类型构造函数Monad(高阶)的应用程序.类似地，Monoid[List[Int]]不是类型构造函数，而是对类型构造函数Monoid(一阶)的类型为List[Int]的应用程序.高阶类型构造器被称为HKT.谈论HKT并指向一个具体的解析类型(它是通过应用某种类型构造函数而创建的)是没有意义的.
I'm reading through the Functional Programming in Scala book and in the Monoids chapter, they talk about a Monoid interface that looks like this:
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
Later on, they define specific Monoid instances by extending this interface. For example.,
val intMonoid = new Monoid[Int] {
...
}
val listMonoid = new Monoid[List[Int]] {
...
}
A couple more pages that I read through this chapter 10, I come across 'higher kinded types' which according to the book is any type that it self is a type that can take other types.
trait Foldable[F[_]] {
...
...
}
So the trait Foldable is according to the book a higher kinded type. My question is, the Monoid[A] to me is also fits the 'higher kinded type' definition as it can take a List[A]. Is my understanding correct? If not what makes higher kinded types a higher kinded type in Scala?
Edit: So a unary type constructor takes an argument and produces a type. Now what about this case here?
def listMonoid[A] = new Monoid[List[A]] {
...
...
}
So is my listMonoid function a HKT?
Some terminology:
- proper type (e.g. Int)
- first-order type (e.g. List[_]); we could also say first-order kind
- higher-kinded type (e.g. Monad[M[_])
When you say
trait Monoid[A] {
def op(a1: A, a2: A): A
def zero: A
}
val listMonoid = new Monoid[List[Int]] {
def op(l: List[Int], l2: List[Int]) = List(1,2)
def zero = List(1,2)
}
you are parameterizing the Monoid trait with some type A, which can (as you noticed) be a simple type, also know as proper type (e.g. Int) or a parameterized type (e.g. List[Int], or even List[Set[Map[Int, Int]]). This makes Monoid a first-order type. We can also say that it's a unary type constructor - it takes one type to produce the final type.
Unlike Monoid, some abstractions (e.g. Monad) need to be parameterized by a type constructor. Int doesn't work any more. It needs to be "some type than can produce another type". Abstraction which is parameterized by a type constructor (that is, parameterized by a "first-order type") is a higher-kinded type. Here's an example:
trait Monad[M[_]] {
def op[A, B](m: M[A], f: A => M[B]): M[B]
def zero[A](a: A): M[A]
}
object ListMonad extends Monad[List] {
def op[A, B](m: List[A], f: A => List[B]) = m.flatMap(f)
def zero[A](a: A) = List[A](a)
}
val listMonad = ListMonad.zero(42)
val result = ListMonad.op(listMonad, (i: Int) => List(i - 1, i, i + 1))
// result = List(41, 42, 43)
So Monad is parameterized by a first-order type (a unary type constructor), which makes Monad itself a higher-kinded type.
Note how Monad doesn't really care about the "inner type" itself on the class level as it will be defined by the methods op and zero. You could also say trait Monad[M[A]] and "fix" the type A at the point of definition of class ListMonad (e.g. fix it to Int), but then you are losing flexibility (your ListMonad will then only be able to construct and flatMap a List[Int] and you would need a different class for, say, List[String]).
This is different than a Monoid which is not a higher-kinded type; it doesn't need a type constructor to produce a type. If it needed it, then you could never have a, say, Monoid[Int], because Int is not a type constructor.
Note also how I said that Monad needs a unary type constructor, meaning it takes only one type (unlike e.g. Map which takes two). Type constructors are often represented with asterisks and arrows:
- unary first-order type constructor is
* -> *(it takes a single type and produces the final type, e.g. Set) - binary first-order type constructor is
* -> * -> *(a binary type constructor, takes two types to produce the final type, e.g. Map) - unary higher-kinded type is
(* -> *) -> *(takes a single unary type constructor to produce the final type, e.g. Monad)
etc.
So, first-order type takes a simple/concrete/proper type and produces the final type, while higher-kinded type goes one level above; it takes a first-order type to produce the final type.
EDIT:
Answering your question in "edit" part: OK I think I know what's confusing you. listMonoid is not a type, so it can't be a higher-kinded type. It's a method. Monad[List[Int]] is a fully resolved type. Monad[F[A]] is also fully resolved. However, Monad itself is a higher order type.
Let me pull the parallel to functions. If you have a function foo(x: Int), then function invocations such foo(42) or foo(someIntegerValue) result in concrete values. These are the analogous to Monad[List[Int]] and Monad[F[A]]. However, foo itself is a function, just like Monad itself is a type constructor.
If foo takes a simple value (not a function), it's a first-order function; if it takes or returns a function, then it's a higher-order function. Same with type constructors. If it takes a simple type, it's a first-order type constructor. Example: List. If it takes another type constructor, it's a higher-order type constructor (also know as higher-kinded type). Example: Monad.
Don't mix resolved types with type constructors. It makes sense to think whether function foo is higher-order or not; this depends on its arguments and return type. But it makes no sense to think whether foo(42) is higher-order or not; this is not a function, but a function application, which results in value. Monad[List[Int]] is not a type constructor, but an application of type constructor List to the type constructor Monad (which is higher-order). Similarly, Monoid[List[Int]] is not a type constrcutor, but an application of type List[Int] to the type constructor Monoid (which is first-order). Type constructors of higher order are called HKT. It doesn't make sense to talk about HKT and point at a concrete resolved type (that was created as a result of application of some type constructor).
这篇关于Scala中的高级类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
