18

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

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

4

3 回答 3

61

ADT（在这种情况下不是抽象数据类型，甚至是另一个概念，而是代数数据类型）和类型类是完全不同的概念，它们解决不同的问题。

ADT，从首字母缩写词如下，是一种数据类型。需要 ADT 来构建数据。我认为，Scala 中最接近的匹配是案例类和密封特征的组合。这是在 Haskell 中构建复杂数据结构的主要方法。我认为 ADT 最著名的例子是Maybetype：

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-ary，as Nothing/ None；1-ary，as 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]

这是一个简单的二叉树。这两个定义基本上如下：“二叉树要么是 a 要么是Leafa Branch；如果它是一个分支，那么它包含一些值和另外两棵树”。这意味着如果您有一个类型的变量，Tree那么它可以包含 aLeaf或 a 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 = ...

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

这种为现有类型添加类型类实例的能力是解决表达式问题的一种方法。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包装器，所以我不在这里展示它。

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

于 2013-09-29T20:36:22.993 回答
8
于 2013-09-29T21:00:02.260 回答
6

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

  • 当您想根据某物的类型分派方法时，请使用类型类
  • 当您想根据某物的价值分派方法时，请使用 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

...print2除非我知道e. 如果e是a，Left那么我选择Left分支，如果e是a，Right那么我选择Right分支。有时我可以静态推断哪个构造函数e将是，但有时我不能，例如在以下示例中：

main = do
    e <- readLn  -- Did I get a 'Left' or 'Right'?
    print2 e     -- Who knows until I run the program
于 2013-09-29T20:26:38.810 回答