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

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]

事实并非如此 选项 是在标准库中定义的,但你明白了。

基本上,ADT是几个命名元组(0-元,如 Nothing / None ; 1-元,作为 Just a / Some(value) ; 更高的arities也是可能的)。

考虑以下数据类型:

-- 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 那么它可以包含 叶 或 树枝 ,如果需要,您可以检查其中的哪一个,并提取包含的数据。这种检查和提取的主要手段是模式匹配:

-- 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 = ...

但是你不能用接口做这样的事情,也就是说,你不能让一个现有的类实现你的接口。正如您也注意到的,这个特性意味着类型类 打开 .

这种为现有类型添加类型类实例的能力是解决问题的一种方法 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] trait对应于类型类,隐式对象定义对应于它的实例。

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

请注意,可以编写与上述Scala程序等效的Haskell程序,但需要编写多个模块或 newtype 包装纸,所以我不在这里展示。

BTW,Clojure,一种在JVM上工作的Lisp方言,已经 协议 ,将接口和类型类组合在一起。协议是在单个第一个参数上调度的,但您可以为任何现有类型实现协议。

你的问题实际上涉及 三 不同的概念: 类型类、抽象数据类型和 代数的 数据类型。 令人困惑的是,“抽象”和“代数”数据类型都可以 简称“ADT”;在Haskell上下文中,ADT几乎总是意味着 “代数”。

让我们定义这三个术语。

代数数据类型(ADT)是一种可以通过组合 更简单的类型。这里的核心思想是“构造函数”,它是一个 定义值的符号。将其视为 Java风格的枚举,但它也可以接受参数。最简单的 代数数据类型只有一个没有参数的构造函数:

data Foo = Bar

这种类型的值只有一个: Bar 就其本身而言,这并不是很有趣;我们需要一些方法来建立更大的类型。

第一种方法是给出我们的构造函数参数。例如,我们可以 酒吧 s取一个int和一个字符串:

data Foo = Bar Int String

现在 Foo 具有许多不同的可能值: Bar 0 "baz" , Bar 100 "abc" 等等。一个更现实的例子可能是一个员工的记录,看起来像这样:

data Employee = Employee String String Int

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

data Foo = Bar
         | Baz

现在是类型的值 Foo公司 可以是任意一种 酒吧 或 巴兹 。事实上 确切地 布尔运算是如何工作的; Bool 定义如下:

data Bool = True
          | False

它的工作方式正是你所期望的。真正有趣的类型可以使用这两种方法来组合它们自己。作为一个相当做作的例子,想象一下形状:

data Shape = Rectangle Point Point
           | Circle Point Int

形状可以是由其两个角定义的矩形,也可以是作为中心和半径的圆。(我们只是定义 Point 像 (Int, Int) )很公平。但在这里,我们遇到了一个障碍:事实证明 另外 形状也存在!如果一些信奉三角形的异教徒想在他们的模型中使用我们的类型,他们能添加一个吗 Triangle 事后构造函数?不幸的是不是:在Haskell中,代数数据类型是 关闭 ,这意味着你不能在事后添加新的替代方案。

使用代数数据类型可以做的一件重要事情是 图案匹配 这基本上意味着能够在ADT的替代方案上进行分支。作为一个非常简单的例子,您可以在上进行模式匹配,而不是使用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

这个 _ 只是意味着我们不在乎点的中心值。

这只是代数数据类型的基本概述:事实证明,还有更多的乐趣。你可能想看看 relevant chapter 在里面 让你成为哈斯克尔 (简称LYAH)以获取更多阅读。

现在,怎么样 摘要 数据类型?这指的是一个不同的概念。抽象数据类型是实现不公开的类型:您不知道该类型的值实际是什么样子的。你唯一能做的就是应用从它的模块导出的函数。你不能在上面进行模式匹配,也不能自己构建新的价值观。实践中的一个很好的例子是 Map (来自 Data.Map ). 映射实际上是一种特定类型的二进制搜索树,但模块中没有任何内容允许您直接使用树结构。这一点很重要,因为树需要维护某些额外的不变量,而这些不变量很容易被搞砸。所以你只会使用 地图 作为不透明的斑点。

代数类型和抽象类型在某种程度上是正交的概念;很不幸的是,他们的名字很容易让人把其中一个误认为另一个。

拼图的最后一块是 类型类 。与代数和抽象数据类型不同,类型类本身不是类型。更确切地说,将类型类视为 设置 类型。特别是,类型类是实现某些函数的所有类型的集合。

最简单的例子是 Show ,它是具有字符串表示的所有类型的类;也就是说,所有类型 a 我们有一个函数 show ∷ a → String 。如果类型具有 show 函数,我们说它是“in” 显示 “否则就不是了。你认识的大多数类型都喜欢 Int , 布尔 和 String 都在 显示 ; 另一方面,函数(具有 → )是 不 在里面 显示 。这就是GHCi无法打印函数的原因。

类型类是由类型需要实现的函数来定义的。例如, 显示 可以通过 显示 功能:

class Show a where
  show ∷ a → String

现在添加一个新类型,如 Foo公司 到 显示 ,我们必须写一个 例子 这是 显示 功能:

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

在此之后, Foo公司 在中 显示 。我们可以为 Foo公司 在任何地方特别是,我们可以在定义类之后编写新的实例,甚至在其他模块中也是如此。这就是类型类的意义 打开 ; 与代数数据类型不同,我们可以在事实之后向类型类添加新的东西。

还有更多的类型类;你可以在 same LYAH chapter .

从技术上讲,还有另一个值叫做(bottom),但我们现在将忽略它。你可以稍后了解。

实际上, 显示 实际上还有另一个可能的函数 列表 属于 一 s到a 一串 。这基本上是一个让字符串看起来很漂亮的破解方法,因为字符串只是 Char s而不是它自己的类型。

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

• 当您想要基于某个对象的 类型
• 当您想要基于某个对象的 价值

例如,考虑 print 功能:

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

类型是静态的,在程序的整个生命周期内不能更改,因此,当您使用类型类时,您使用的方法在编译时会根据调用站点上推断的类型进行静态选择。所以在这个例子中,我知道我正在使用 Char 的实例 Show 甚至不用运行程序:

main = print 'C'

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

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

现在,如果我打电话 print2 在某些情况下:

print2 e

…我不知道是哪个分支 打印2 除非我知道的运行时值 e 。如果 e 是一个 Left 然后我拿 左边 分支和if e 是一个 Right 然后我拿 正确的 树枝有时我可以静态地推理哪个构造函数 e 会,但有时我做不到,例如以下示例:

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