logo标签列表

Scala：类型类和ADT的区别是什么？

scalahaskelltypeclassabstract-data-typestructural-typing
18

类型类(Typeclasses)和抽象数据类型(Abstract Data Types)有什么区别？

我知道这对于Haskell程序员来说是基本的东西，但我来自Scala背景，希望能举出Scala的例子。目前我所找到的最好的解释是，类型类是“开放”的，而ADT则是“封闭”的。与结构类型进行比较和对比也会很有帮助。

4
你是不是指“代数数据类型”？ - Carl
抱歉，在面向对象的世界中，ADT通常指抽象数据类型，但在函数式编程的世界中，它表示代数数据类型，所以我有点困惑。感谢大家澄清这一点。 - James McCabe
3个回答
63
ADTs（在此上下文中不是抽象数据类型，而是代数数据类型）和类型类是完全不同的概念，解决了不同的问题。
ADT，从首字母缩写可以看出，它是一种数据类型。需要使用 ADT 来结构化数据。我认为，在 Scala 中最接近 ADT 的概念是一个 case class 和 sealed trait 的组合。这也是 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)

但我认为这超出了这个问题的范围。如果你想了解更多，我可以搜索一些链接。
另一方面，类型类是定义多态行为的一种方式。大致上，类型类是某些类型提供的契约。例如，您知道您的值 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 = ...

但是你不能使用接口来做这样的事情，也就是说，你不能让一个已经存在的类实现你的接口。正如你也注意到的那样，这个特性意味着类型类是开放的。
为现有类型添加类型类实例的能力是解决表达式问题的一种方式。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方言，具有协议（protocols）的概念，将接口和类型类结合起来。协议是在单个第一个参数上调度的，但您可以为任何现有类型实现协议。
1
如果您对数字/数据类型的对应关系感兴趣，代数数据类型的代数，第1部分是一个很好的起点。 - kqr
1
非常好的回答，感谢您花时间编写Scala和Haskell示例。 - James McCabe
8
你的问题实际上涉及到三个不同的概念：类型类、抽象数据类型和代数数据类型。令人困惑的是，“抽象”和“代数”数据类型都可以缩写为“ADT”; 在Haskell环境中，“ADT”几乎总是指“代数数据类型”。
所以让我们定义这三个术语。
代数数据类型（ADT）是一种可以通过组合更简单的类型来创建的类型。核心思想在于“构造函数”，它是定义值的符号。将其视为Java样式枚举中的值，但它还可以带有参数。最简单的代数数据类型只有一个没有参数的构造函数。
data Foo = Bar

这种类型只有一个值： Bar。单独使用并不是非常有趣，我们需要一些方法来构建更大的类型。

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

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
_只是表示我们不关心点的中心值。
这只是关于代数数据类型的基本概述：事实上还有更多的乐趣可寻。您可能需要查看 Learn You a Haskell（LYAH）中的相关章节以获取更多阅读材料。
那么抽象数据类型怎么样呢？这是指不同的概念。抽象数据类型是一种未公开实现的类型：您不知道类型的值实际上是什么样子的。您能做的唯一事情就是应用从其模块中导出的函数。您无法对其进行模式匹配或自己构建新值。实践中一个很好的例子是Map（来自于Data.Map）。该映射实际上是特定类型的二叉搜索树，但模块中没有任何内容让您直接使用该树结构。这很重要，因为树需要保持某些额外的不变性，您很容易弄乱它们。因此，您只能将Map作为不透明的blob使用。
代数和抽象类型是有些正交的概念；不幸的是，它们的名称使得很容易混淆它们。
最后一个要点是typeclass。与代数和抽象数据类型不同，类型类本身并不是一种类型。相反，将类型类视为一组类型的集合。特别地，类型类是实现特定函数的所有类型的集合。
最简单的例子是 Show，它是具有字符串表示形式的所有类型的类；也就是说，对于我们有一个函数show ∷ a → String的所有类型a。如果类型具有show函数，我们说它"在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 编写实例。特别是，在类已被定义之后，甚至在其他模块中也可以编写新的实例。这就是类型类“开放”的含义；与代数数据类型不同，我们可以在事后向类型类添加新内容。
类型类还有更多内容；您可以在相同的LYAH章节中了解它们。
¹ 严格来说，还有另一个值叫做 ⊥（底部），但现在我们将忽略它。您可以稍后了解 ⊥。
² 实际上，Show 还有另一个可能的函数，它将 列表 的 a 转换为 String。这基本上是一种 hack，使字符串看起来漂亮，因为字符串只是 Char 的列表而不是它自己的类型。
6

类型类和ADT的区别在于：

  • 当您想要基于某个类型分派方法时，请使用类型类
  • 当您想要基于某个值分派方法时，请使用ADT

例如，考虑print函数：

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

类型是静态的，不能在程序的整个生命周期内改变，因此当您使用类型类时，基于调用点推断的类型，在编译时静态选择要使用的方法。因此，在这个例子中，我知道即使没有运行程序，我正在使用Show的Char实例：

main = print 'C'

抽象数据类型可以动态地改变函数的行为。例如，我可以定义：

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

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

我无法知道print2使用哪个分支，除非我知道e的运行时值。如果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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接