Jam*_*abe 13 haskell scala abstract-data-type typeclass structural-typing
类型类和抽象数据类型之间有什么区别？
我意识到这对于Haskell程序员来说是一个基本的东西,但我来自Scala背景,并且会对Scala中的示例感兴趣.我现在能找到的最好的是类型类是"开放的"而ADT是"封闭的".将类型类与结构类型进行比较和对比也是有帮助的.
Vla*_*eev 51
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-ary,as Nothing/ None; 1-ary,as 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]
这是简单的二叉树.这两个定义基本上都是如下:"二叉树是a Leaf或a 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] trait对应于类型类,隐式对象定义对应于其实例.
如您所见,类型类是一种接口,但功能更强大.您甚至可以选择类型类的不同实现,而使用它们的代码保持不变.然而,这种功率是以样板和额外实体为代价的.
请注意,可以编写与上面Scala程序等效的Haskell,但是它需要编写多个模块或newtype包装器,所以我不在这里介绍它.
BTW,Clojure,一个在JVM上工作的Lisp方言,有协议,它结合了接口和类型类.协议是在单个第一个参数上调度的,但您可以为任何现有类型实现协议.
您的问题实际上涉及三个不同的概念:类型类,抽象数据类型和代数数据类型.令人困惑的是,"抽象"和"代数"数据类型都可以缩写为"ADT"; 在Haskell上下文中,ADT几乎总是意味着"代数".
所以让我们定义所有三个术语.
代数数据类型(ADT)是可以通过组合更简单的类型来实现的类型.这里的核心思想是"构造函数",它是一个定义值的符号.可以把它想象成Java风格的枚举中的值,除了它也可以带参数.最简单的代数数据类型只有一个没有参数的构造函数:
data Foo = Bar
这种类型只有一个¹值:Bar.就其本身而言,这并不是很有趣; 我们需要一些方法来建立更大的类型.
第一种方法是给出构造函数参数.例如,我们可以Bar使用int和字符串:
data Foo = Bar Int String
现在Foo有很多不同的可能值:Bar 0 "baz",Bar 100 "abc"等等.一个更现实的例子可能是员工的记录,看起来像这样:
data Employee = Employee String String Int
构建更复杂类型的另一种方法是通过多个构造函数进行选择.例如,我们可以同时拥有a Bar 和 a 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的替代品.作为一个非常简单的示例,您可以使用if表达式进行模式匹配,而不是使用if表达式Bool:
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
这_意味着我们不关心点中心的价值.
这只是代数数据类型的基本概述:事实证明,它有了更多的乐趣.您可能需要查看" 了解你的Haskell"(简称LYAH)中的相关章节以获得更多阅读.
现在,抽象数据类型呢？这指的是一个不同的概念.抽象数据类型是未公开实现的类型:您不知道类型的值实际上是什么样的.你唯一能做的就是应用从模块中导出的函数.您无法对其进行模式匹配或自行构建新值.实践中的一个好例子是Map(来自Data.Map).该映射实际上是一种特殊的二叉搜索树,但模块中没有任何内容可以让您直接使用树结构.这很重要,因为树需要维护某些额外的不变量,这些变量很容易搞乱.所以你只能Map用作不透明的blob.
代数和抽象类型在某种程度上是正交的概念; 相当不幸的是,他们的名字很容易将一个人误认为另一个人.
拼图的最后一部分是类型类.与代数和抽象数据类型不同,类型类本身不是类型.相反,将类型类视为一组类型.特别是,类型类是实现某些功能的所有类型的集合.
最简单的例子是Show,它是具有字符串表示的所有类型的类; 也就是说,a我们有一个功能的所有类型show ? a ? String.如果一个类型有一个show函数,我们说它是"in Show"; 否则,它不是.你知道的大多数类型都是Int,Bool并且String都在Show; 另一方面,函数(任何带有a的类型?)都不在Show.这就是GHCi无法打印功能的原因.
类型类由一个类需要实现的函数定义为它的一部分.例如,Show可以通过show函数定义² :
class Show a where
show ? a ? String
现在添加一个新的类型一样Foo来Show,我们来写一个例子吧.这是show函数的实际实现:
instance Show Foo where
show foo = case foo of
Bar ? "Bar"
Baz ? "Baz"
在此之后,Foo是在Show.我们可以在Foo任何地方编写实例.特别是,我们可以在定义类之后编写新实例,即使在其他模块中也是如此.这就是类型类开放的意义 ; 与代数数据类型不同,我们可以在事后添加新的东西给类型类.
对于类型类还有更多; 你可以在同一个LYAH章节中阅读它们.
¹从技术上讲,还有另一个名为⊥(底部)的值,但我们暂时忽略它.你可以稍后了解⊥.
²在现实中,Show其实有另一种可能的函数,它接受一个列表的as到一个String.这基本上是一个让字符串看起来很漂亮的黑客,因为字符串只是一个Chars 列表而不是它自己的类型.
类型类和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是,Right那么我拿Right分支.有时我可以静态地推断出哪个构造函数e会,但有时我不能,例如在下面的例子中:
main = do
e <- readLn -- Did I get a 'Left' or 'Right'?
print2 e -- Who knows until I run the program