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

Question

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

我知道这是Haskell程序员的基础知识，但我有Scala背景，我会对Scala中的示例感兴趣。我现在所能找到的最好的是类型类是“开放的”，而ADT的是“关闭的”。将类型类与结构类型进行比较和对比也很有帮助。

Answer 1

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

ADT是一种数据类型，其缩写如下。ADT是构建数据结构所必需的。我认为在Scala中最接近的匹配是case类和密封特征的组合。这是在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)；更高的元组也是可能的)。

考虑以下数据类型：

-- 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)

但我认为这超出了这个问题的范围。如果你想知道更多，我可以搜索一些链接。

另一方面，类型类是定义多态行为的一种方式。粗略地说，类型类是某些类型提供的契约。例如，您知道您的value x满足定义某些操作的约定。然后，您可以调用该方法，然后自动选择该协定的实际实现。

通常将类型类与Java接口进行比较，例如：

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

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

// Scala
trait Show {
  def show: String
}

通过这种比较，类型类的实例与接口的实现相匹配：

-- 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"
}

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

class MyShow a where
  myShow :: a -> String

instance MyShow Int where 
  myShow x = ...

但是你不能对接口做这样的事情，也就是说，你不能让现有的类实现你的接口。正如您也注意到的，此功能意味着类型类是开放的。

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

类型类和接口之间的另一个区别是，接口只在第一个参数上是多态的，即隐式this。类型类在这个意义上不受限制。您可以定义甚至在返回值上进行调度的类型类：

class Read a where
  read :: String -> a

使用接口不可能做到这一点。

可以使用隐式参数在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]特征对应于类型类，隐式对象定义对应于它的实例。

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

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

顺便说一句，Clojure是一种工作在JVM上的Lisp方言，它有结合了接口和类型类的协议。协议是在单个第一个参数上调度的，但您可以为任何现有类型实现协议。

Answer 2

你的问题实际上涉及到三个不同的概念:类型类、抽象数据类型和代数数据类型。令人困惑的是，“抽象”和“代数”数据类型都可以缩写为" ADT "；在Haskell上下文中，ADT几乎总是意味着“代数”。

因此，让我们定义这三个术语。

代数数据类型(ADT)是一种可以通过组合更简单的类型来生成的类型。这里的核心思想是“构造函数”，它是一个定义一个值的符号。可以将其视为Java样式枚举中的值，只是它还可以接受参数。最简单的代数数据类型只有一个没有参数的构造函数：

data Foo = Bar

此类型只有一个²值：Bar。就其本身而言，这并不是很有趣；我们需要一些方法来构建更大的类型。

第一种方法是给我们的构造函数参数。例如，我们可以让我们的Bars接受一个整数和一个字符串：

data Foo = Bar Int String

现在Foo有许多不同的可能值：Bar 0 "baz"、Bar 100 "abc"等等。一个更实际的示例可能是员工的记录，如下所示：

data Employee = Employee String String Int

构建更复杂类型的另一种方法是有多个构造函数可供选择。例如，我们可以同时拥有Bar和Baz

data Foo = Bar
         | Baz

现在，Foo类型的值可以是Bar或Baz。这实际上就是布尔值的工作方式；Bool的定义如下：

data Bool = True
          | False

它的工作方式完全符合您的预期。真正有趣的类型可以使用这两种方法来组合它们自己。作为一个相当人为的例子，想象一下形状：

data Shape = Rectangle Point Point
           | Circle Point Int

形状可以是由两个角定义的矩形，也可以是圆心和半径的圆。(我们只将Point定义为(Int, Int)。)当然可以。但在这里，我们遇到了一个问题:原来还存在其他形状！如果一些相信三角形的异端想在他们的模型中使用我们的类型，他们可以在事实之后添加一个Triangle构造函数吗？不幸的是没有:在Haskell中，代数数据类型是封闭的，这意味着您不能在事后添加新的替代方案。

对于代数数据类型，可以做的一件重要的事情就是对其进行模式匹配。这基本上意味着能够在ADT的替代方案上进行分支。作为一个非常简单的示例，您可以在Bool上进行模式匹配，而不是使用if表达式

case myBool of
  True  → ... -- true case
  False → ... -- false case

如果构造函数有参数，也可以通过模式匹配来访问这些值。使用上面的Shape，我们可以编写一个简单的area函数：

area shape = case shape of
  Rectange (x₁, y₁) (x₂, y₂) → (x₂ - x₁) * (y₂ - y₁)
  Circle _ r                 → π * r ^ 2

_只是意味着我们不关心一个点的中心值。

这只是代数数据类型的基本概述:事实证明，还有更多的乐趣。你可能想看看学习哈斯克尔(简称LYAH)中的relevant chapter，以获得更多的阅读。

现在，抽象数据类型呢？这指的是不同的概念。抽象数据类型是不公开实现的类型:您不知道该类型的值实际是什么样子的。您可以使用它做的唯一事情就是应用从它的模块导出的函数。你不能对它进行模式匹配，也不能自己构造新值。实践中的一个很好的例子是Map (来自Data.Map)。映射实际上是一种特殊的二进制搜索树，但是模块中的任何内容都不允许您直接使用树结构。这一点很重要，因为树需要维护某些额外的不变量，这很容易搞砸。因此，您只会将Map用作不透明的blob。

代数类型和抽象类型在某种程度上是正交的概念；不幸的是，它们的名称很容易将两者混淆。

拼图的最后一块是类型类。与代数和抽象数据类型不同，类型类本身不是类型。相反，可以将类型类看作是一组类型。特别是，类型类是实现某些功能的所有类型的集合。

最简单的例子是Show，它是具有字符串表示的所有类型的类；也就是说，我们有一个函数show ∷ a → String来表示所有类型的a。如果一个类型有一个show函数，我们说它是"in Show"；否则，它不是。你知道的大多数类型，如Int，Bool和String都在Show中；另一方面，函数(任何带有→的类型)都不在Show中。这就是GHCi不能打印函数的原因。

类型类是由类型需要实现的函数来定义的。例如，Show可以仅由show函数定义²：

class Show a where
  show ∷ a → String

现在，要向Show添加一个像Foo这样的新类型，我们必须为它编写一个实例。这是show函数的实际实现：

instance Show Foo where
  show foo = case foo of
    Bar → "Bar"
    Baz → "Baz"

在此之后，Foo在Show中。我们可以为Foo anywhere编写一个实例。特别是，我们可以在定义类之后编写新的实例，即使在其他模块中也是如此。这就是开放类型类的含义；与代数数据类型不同，我们可以在事后向类型类添加新的东西。

还有更多关于类型类的内容；您可以在same LYAH chapter中阅读有关它们的内容。

？从技术上讲，还有一个名为⊥(底部)的值，但我们暂时忽略它。您可以稍后了解⊥。

²实际上，Show实际上还有另一个可能的函数，可以将a列表转换为String。这基本上是一种让字符串看起来更漂亮的技巧，因为字符串只是Char的列表，而不是它自己的类型。

Answer 3

类型类和ADT之间的区别是：

当您想要基于某个对象的type

• Use ADT来调度一个方法时，当您想要基于某个对象的value

来调度一个方法时，

• 使用类型类

例如，考虑print函数：

print :: (Show a) => a -> IO ()

类型是静态的，在程序的整个生命周期中不能更改，因此，当您使用类型类时，您使用的方法是在编译时根据调用点处推断出的类型静态选择的。因此，在这个示例中，我知道我使用的是Show的Char实例，甚至没有运行程序：

main = print 'C'

ADT允许您动态更改函数的行为。例如，我可以定义：

print2 :: Either Char String -> IO ()
print2 (Left  c  ) = putStrLn [c]
print2 (Right str) = putStrLn str

现在，如果我在某些上下文中调用print2：

print2 e

..。除非我知道e的运行时值，否则我不知道print2采用哪个分支。如果e是Left，则我采用Left分支，如果e是Right，则我采用Right分支。有时我可以静态地推断e将是哪个构造函数，但有时我不能，例如在下面的示例中：

main = do
    e <- readLn  -- Did I get a 'Left' or 'Right'?
    print2 e     -- Who knows until I run the program