BMe*_*eph 12 haskell types existential-type typeclass
我阅读了William Cook的"On Data Abstraction,Revisited",并重读了Ralf Laemmel的"表达引理",试图理解如何在Haskell中应用前一篇论文的思想.所以,我试图理解你如何在没有指定类型的情况下在Haskell中实现例如集合联合函数？
C. *_*ann 14
有多种方法,取决于您所追求的"抽象数据类型"的版本.
混凝土但不透明的类型:我读了库克的可爱纸张已经有一段时间了,但回头看看它我认为这与他所说的ADT最接近.在Haskell中执行此操作的标准方法是导出没有其构造函数的类型; 这在Haskell中意味着什么:
在抽象类型的值上没有模式匹配
除了使用从其模块导出的函数之外,没有该类型的构造值
这与库克的论文有何关系:
表示独立性:从外部来看,表示是不可访问的.
检查多个表示:在ADT模块内部,可以自由地检查表示.
独特的实现/模块:不同的模块可以提供不同的实现,但除了通常的方法之外,类型不能互操作.您不能Data.IntMap.null用来查看a是否Data.Map.Map Int a为空.
此技术广泛用于Haskell标准库,特别是对于需要维护某种不变量或以其他方式限制构造值的能力的数据类型.所以在这种情况下,从文件中实现设置ADT的最佳方法是以下代码:
import qualified Data.Set as S
虽然这可能不像一个具有更具表现力的模块系统的语言那样强大的抽象手段.
存在量化和接口:Haskell实际上并没有这样的exists关键字,但术语"存在"在各种情况下用于描述某些类型的多态类型.在每种情况下的一般想法是将值与在其上运行的函数集合组合,使得结果在值的类型中是多态的.考虑这个函数签名:
foo :: (a, a -> Bool) -> Bool
虽然它接收一个类型的值a,因为它a是完全多态的,它可以用该值唯一可以做的就是将函数应用于它.所以从某种意义上说,在这个函数中,元组的前半部分是"抽象数据类型",而后半部分是用于处理该类型的"接口".我们可以使这个想法明确,并使用存在的数据类型将其应用于单个函数之外:
data FooADT = forall a. FooADT a (a -> Bool)
foo :: FooADT -> Bool
现在,FooADT只要我们有一个类型的值,我们所知道的是存在一些类型a,以便我们可以将FooADT第二个参数应用于它的第一个.
同样的想法适用于具有类约束的多态类型; 唯一的区别是对类型进行操作的函数是由类类型隐式提供的,而不是与值明确捆绑在一起.
现在,这对库克的论文意味着什么？
代表性独立性仍然适用.
完全隔离:与以前不同,存在量化类型的知识永远丢失.没有什么可以检查表示,除了它自己提供的接口.
任意实现:不仅实现不一定是唯一的,根本没有办法限制它们!任何可以提供相同界面的东西都可以包含在存在主义内部,并且与其他值无法区分.
简而言之,这与库克对物体的描述非常相似.有关存在性ADT的更多信息,本文展开抽象数据类型并不是一个糟糕的起点; 但请记住,它所讨论的内容根本不是库克称之为ADT的内容.
还有一个简短的附录:我已经解决了上面描述存在类型抽象的所有麻烦,我想强调一下FooADT类型:因为所有你能用它做的就是应用函数得到一个Bool结果,从根本上没有区别之间FooADT和之间Bool,除了前者模糊你的代码并需要GHC扩展.在开始在Haskell代码中使用存在类型之前,我强烈建议您阅读此博客文章.