scala - Scala:类型类和ADT之间的区别？

Question

类型类和抽象数据类型之间有什么区别？

我意识到这对Haskell程序员来说是一件基本的事情，但是我来自Scala背景，并且会对Scala中的示例感兴趣。我现在能找到的最好的情况是类型类是“开放的”，而ADT是“封闭的”。将类型类与结构类型进行比较和对比也将很有帮助。

Answer 1

ADT(在本文中不是抽象数据类型，它甚至不是另一个概念，而是代数数据类型)和类型类是解决不同问题的完全不同的概念。

首字母缩写词如下所示，ADT是一种数据类型。需要ADT来构建数据。我认为，Scala中最接近的匹配是案例类和密封特性的组合。这是在Haskell中构造复杂数据结构的主要手段。我认为ADT最著名的例子是Maybe类型:

data Maybe a = Nothing | Just a

此类型在标准Scala库中具有直接等效项，称为 Option:

sealed trait Option[+T]
case class Some[T](value: T) extends Option[T]
case object None extends Option[Nothing]

这不是在标准库中定义 Option的确切方式，但是您明白了。

基本上，ADT是(在某种意义上)多个命名元组的组合(0元，如 Nothing / None； 1元，如 Just a / Some(value)；也可以使用更高的Arity)。

考虑以下数据类型:

-- Haskell
data Tree a = Leaf | Branch a (Tree a) (Tree a)

// Scala
sealed trait Tree[+T]
case object Leaf extends Tree[Nothing]
case class Branch[T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]

这是简单的二叉树。这两个定义的基本含义如下:“二叉树要么是 Leaf要么是 Branch；如果它是分支，则它包含一些值和另外两个树”。这意味着如果您具有类型 Tree的变量，则它可以包含 Leaf或 Branch，并且可以检查其中是否存在一个变量，并根据需要提取包含的数据。此类检查和提取的主要手段是模式匹配:

-- Haskell
showTree :: (Show a) => Tree a -> String
showTree tree = case tree of
  Leaf                    -> "a leaf"
  Branch value left right -> "a branch with value " ++ show value ++ 
                             ", left subtree (" ++ showTree left ++ ")" ++
                             ", right subtree (" ++ showTree right ++ ")"

// Scala
def showTree[T](tree: Tree[T]) = tree match {
  case Leaf => "a leaf"
  case Branch(value, left, right) => s"a branch with value $value, " +
                                     s"left subtree (${showTree(left)}), " +
                                     s"right subtree (${showTree(right)})"
}

这个概念很简单，但也很强大。

如您所知，ADT是关闭的，即，在定义类型之后，您不能添加更多的命名元组。在Haskell中，这是强制执行的语法，而在Scala中，这是通过 sealed关键字实现的，该关键字禁止其他文件中的子类。

这些类型由于某种原因被称为代数。命名的元组可以被认为是乘积(在数学意义上)，而这些元组的“组合”可以作为求和(也在数学意义上)，并且这种考虑具有深厚的理论意义。例如，上述的二叉树类型可以这样写:

Tree a = 1 + a * (Tree a) * (Tree a)

但是我认为这超出了这个问题的范围。如果您想了解更多信息，我可以搜索一些链接。

另一方面，类型类是定义多态行为的一种方式。大致类型类别是某些类型提供的合同。例如，您知道自己的值 x满足定义某些操作的合同。然后，您可以调用该方法，然后自动选择该合同的实际实现。

通常将类型类与Java接口(interface)进行比较，例如:

-- Haskell
class Show a where
    show :: a -> String

// Java
public interface Show {
    String show();
}

// Scala
trait Show {
  def show: String
}

使用此比较，类型类的实例与接口(interface)的实现相匹配:

-- Haskell
data AB = A | B

instance Show AB where
  show A = "A"
  show B = "B"

// Scala
sealed trait AB extends Show
case object A extends AB {
  val show = "A"
}
case object B extends AB {
  val show = "B"
}

接口(interface)和类型类之间有非常重要的区别。首先，您可以编写自定义类型类并使任何类型成为其实例:

class MyShow a where
  myShow :: a -> String

instance MyShow Int where 
  myShow x = ...

但是您不能使用接口(interface)来做这种事情，也就是说，您不能使现有的类实现您的接口(interface)。您也已经注意到，此功能意味着类型类是打开的。

这种为现有类型添加类型类实例的能力是解决 expression problem的一种方法。 Java语言没有解决它的方法，但是Haskell，Scala或Clojure有解决方法。

类型类和接口(interface)之间的另一个区别是，接口(interface)仅在第一个参数(即隐式 this)上是多态的。类型类在这种意义上不受限制。您可以定义类型类，即使在返回值时也可以调度:

class Read a where
  read :: String -> a

使用接口(interface)无法做到这一点。

可以使用隐式参数在Scala中模拟类型类。这种模式非常有用，以至于在最新的Scala版本中甚至有一种特殊的语法可以简化其用法。这是完成的方式:

trait Showable[T] {
  def show(value: T): String
}

object ImplicitsDecimal {
  implicit object IntShowable extends Showable[Int] {
    def show(value: Int) = Integer.toString(value)
  }
}

object ImplicitsHexadecimal {
  implicit object IntShowable extends Showable[Int] {
    def show(value: Int) = Integer.toString(value, 16)
  }
}

def showValue[T: Showable](value: T) = implicitly[Showable[T]].show(value)
// Or, equivalently:
// def showValue[T](value: T)(implicit showable: Showable[T]) = showable.show(value)

// Usage
{
  import ImplicitsDecimal._
  println(showValue(10))  // Prints "10"
}
{
  import ImplicitsHexadecimal._
  println(showValue(10))  // Prints "a"
}

Showable[T]特征对应于类型类，隐式对象定义对应于其实例。

如您所见，类型类是一种接口(interface)，但功能更强大。您甚至可以选择类型类的不同实现，而使用它们的代码将保持不变。然而，这种能力是以样板和额外实体为代价的。

请注意，可以编写与上述Scala程序等效的Haskell，但是它将需要编写多个模块或 newtype包装器，因此在此不做介绍。

BTW，Clojure，一种在JVM上运行的Lisp方言，具有协议(protocol)，该协议(protocol)结合了接口(interface)和类型类。协议(protocol)是在单个第一个参数上分派(dispatch)的，但是您可以为任何现有类型实现协议(protocol)。