Scala中的类型级别编程 [英] Type Level Programming in Scala

问题描述

我想更深入地学习Scala的类型级别编程，并且我开始做一些小练习.我从类型级别的Peano数字实现开始.这是下面的代码！

sealed trait PeanoNumType { // Type at the end indicates to the reader that we are dealing with types
  type plus[That <: PeanoNumType] <: PeanoNumType
}

sealed trait ZeroType extends PeanoNumType {
  type plus[That <: PeanoNumType] = That
}

sealed trait NextType[This <: PeanoNumType] extends PeanoNumType {
   type plus[That <: PeanoNumType] = NextType[This#plus[That]]
}

现在的问题是，上述实施方案能给我带来什么好处?我该如何利用它?

解决方案

只要您需要自己创建这些类型，它就不会给您带来太多好处.但是，一旦让编译器为您完成这些工作，它将变得更加有用.

在向我展示这个之前，让我们将代表Peano的算术形式更改为更短的形式:

sealed trait Num
case object Zero extends Num
case class Succ[N <: Num](num: N) extends Num

然后您可以创建一个在编译时已知大小的列表:

sealed abstract class List[+H, N <: Num](val size: N) {
  def ::[T >: H](value: T): List[T, Succ[N]] = Cons(value, this)
}
case object Nil extends List[Nothing, Zero.type](Zero)
case class Cons[+H, N <: Num](head: H, tail: List[H, N]) extends List[H, Succ[N]](Succ(tail.size))
type ::[+H, N <: Num] = Cons[H, N]

如果您检查使用sych列表创建的某物的类型，它将以其类型进行编码:

val list = 1 :: 2 :: 3 :: 4 :: Nil // List[Int, Succ[Succ[Succ[Succ[Zero.type]]]]] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))

接下来您可以尝试做的事情是使用隐式函数来检查某项内容，例如

trait EvenNum[N <: Num]
implicit val zeroIsEven = new EvenNum[Zero.type] {}
implicit def evenNPlusTwo[N <: Num](implicit evenN: EvenNum[N]) = new EvenNum[Succ[Succ[N]]] {}

这样，您可以强制执行某些操作，只有在可以提供隐式证据时才可以执行:

def operationForEvenSizeList[T, N <: Num](list: List[T, N])(implicit ev: EvenNum[N]) = {
  // do something with list of even length
}

operationForEvenSizeList(1 :: 2 :: Nil) // ok
operationForEvenSizeList(1 :: 2 :: 3 :: Nil) // compiler error

据我所知，当您开始使用隐式来创建新类型时，Scala中的类型级编程的真正威力便出现了:您可以将它们用于隐式证据，类型类派生和某些结构化样板的删除./p>

Shapeless是帮助通用编程的库.我相信，一旦您使用隐式的某些类型类派生进行一两个练习之后，对您来说这将是一件有趣的事情.

回到您的代码:您可以提供一些隐式函数，这些隐式函数将为您生成并提供类的实例.另外，除了创建新类，此代码还将执行其他操作，例如组合您将在这些类中添加的元素列表，或者提供从PeanoNumType到Int的转换，或者添加一些在编译时起作用的谓词，等等.

I wanted to get deeper into type level programming in Scala and I started doing some small exercises. I started with an implementation of Peano numbers at the type level. Here is the code below!

sealed trait PeanoNumType { // Type at the end indicates to the reader that we are dealing with types
  type plus[That <: PeanoNumType] <: PeanoNumType
}

sealed trait ZeroType extends PeanoNumType {
  type plus[That <: PeanoNumType] = That
}

sealed trait NextType[This <: PeanoNumType] extends PeanoNumType {
   type plus[That <: PeanoNumType] = NextType[This#plus[That]]
}

Now the question is, what would the above implementation buy me? How can I make use of it?

解决方案

As long as you need to create those types yourself, it doesn't give you much. But, as soon as you make compiler do the stuff for you, it will be much more useful.

Before I show this, let's change a way of representing Peano aritmetic into something shorter:

sealed trait Num
case object Zero extends Num
case class Succ[N <: Num](num: N) extends Num

You could then create list with a size known at compile time:

sealed abstract class List[+H, N <: Num](val size: N) {
  def ::[T >: H](value: T): List[T, Succ[N]] = Cons(value, this)
}
case object Nil extends List[Nothing, Zero.type](Zero)
case class Cons[+H, N <: Num](head: H, tail: List[H, N]) extends List[H, Succ[N]](Succ(tail.size))
type ::[+H, N <: Num] = Cons[H, N]

If you check the type of sth created with sych list it will have size encoded in its type:

val list = 1 :: 2 :: 3 :: 4 :: Nil // List[Int, Succ[Succ[Succ[Succ[Zero.type]]]]] = Cons(1,Cons(2,Cons(3,Cons(4,Nil))))

Next thing you could try to do would be usage of implicits to check something, e.g.

trait EvenNum[N <: Num]
implicit val zeroIsEven = new EvenNum[Zero.type] {}
implicit def evenNPlusTwo[N <: Num](implicit evenN: EvenNum[N]) = new EvenNum[Succ[Succ[N]]] {}

With that you could enforce that some operation could only be done when implicit evidence could be supplied:

def operationForEvenSizeList[T, N <: Num](list: List[T, N])(implicit ev: EvenNum[N]) = {
  // do something with list of even length
}

operationForEvenSizeList(1 :: 2 :: Nil) // ok
operationForEvenSizeList(1 :: 2 :: 3 :: Nil) // compiler error

As far as I can tell true power of type-level programming in Scala appears when you start using implicits for creating new types: ones that you could use for implicit evidence, type-class derivation and removal of some structural boilerplate.

A library helping a lot with generic programming is Shapeless. I believe it will be a fun thing for you to work with, once you will do an exercise or two with some type-class derivation with implicits.

Getting back to your code: you could provide some implicits which would generate and provide instances of your class for you. Also, besides creating new class, this code would also do something else e.g. combine lists of elements you would add in those classes, or provide conversion from PeanoNumType to Int, or add some predicates working in compile time, etc. Sky is the limit.

这篇关于Scala中的类型级别编程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！