如何在Haskell中声明抽象数据容器类型? [英] How does one declare an abstract data container type in Haskell?

问题描述

我阅读了威廉·库克(William Cook)的重新审视数据抽象"，并重新阅读了拉尔夫·拉姆梅尔(Ralf Laemmel)的表达引理"，试图理解如何在Haskell中运用前一篇论文的思想.因此，我试图了解您如何在Haskell中实现(例如，设置联合函数)而不指定类型?

解决方案

有多种方法，具体取决于要使用的抽象数据类型"的版本.

• 具体但不透明的类型:自从我读了Cook的可爱论文已经有一段时间了，但是回头看一看，我认为这与他所说的ADT最接近.在Haskell中执行此操作的标准方法是在不构造函数的情况下导出类型.这在Haskell中是什么意思:

  • 抽象类型的值上没有模式匹配

  • 没有构造类型的值，除非使用从其模块导出的函数

  这与库克的论文有何关系:

  • 表示形式独立性:从外部，无法访问表示形式.

  • 检查多种表示形式:在ADT的模块内部，可以自由检查表示形式.

  • 唯一的实现/模块:不同的模块可以提供不同的实现，但是类型只能通过常规方式进行互操作.您不能使用Data.IntMap.null来查看Data.Map.Map Int a是否为空.

  该技术已在Haskell标准库中广泛使用，特别是对于需要保持某种不变性或限制构造值的能力的数据类型.因此，在这种情况下，从本文中实现集合ADT的最佳方法是以下代码:

  import qualified Data.Set as S
  

  尽管这可能不像具有更富有表现力的模块系统的语言所具有的那样强大的抽象手段.

• 现有量化和接口:Haskell实际上没有exists关键字，但是在各种情况下都使用术语"existential"来描述某些类型的多态类型.在每种情况下，通常的想法是将值与在其上操作的函数的集合组合在一起，以使结果在值的类型上是多态的.考虑以下函数签名:

  foo :: (a, a -> Bool) -> Bool
  

  尽管它接收到类型为a的值，但是由于a是完全多态的，因此唯一可以使用该值执行的操作就是将函数应用于该值.因此，从某种意义上说，在此功能内，元组的前半部分是抽象数据类型"，而后半部分是用于处理该类型的接口".我们可以使这个想法明确，并使用 existential数据类型

  将其应用到单个函数之外:

  data FooADT = forall a. FooADT a (a -> Bool)
  
  foo :: FooADT -> Bool
  

  现在，只要我们拥有类型为FooADT的值，我们所知道的就是存在一些类型为a的东西，这样我们就可以将FooADT的第二个参数应用于其首先.

  相同的想法适用于具有类约束的多态类型；唯一的区别是，对类型进行操作的函数由类型类隐式提供，而不是与值显式捆绑在一起.

  现在，对于库克的论文而言，这意味着什么?

  • 表示独立性仍然适用.

  • 总隔离度:与以前不同，永久量化类型的知识将永远丢失.除了它本身提供的接口之外，没有人可以检查该表示形式.

  • 任意实现:不仅实现不一定是唯一的，而且根本没有办法限制它们！可以提供相同接口的所有内容都可以包装在一个存在对象中，并且无法与其他值区分开.

  简而言之，这与库克对对象的描述非常相似.有关现有ADT的更多信息，请参见展开抽象数据类型开始不是一个坏地方；但请记住，它所讨论的本质上不是Cook所说的ADT.

---

和一个简短的附录:上面的所有麻烦都描述了存在性类型抽象，我想重点介绍一下FooADT类型:因为您所能做的就是应用该函数来获取Bool结果，FooADT和Bool 之间基本上没有任何区别，只是前者使您的代码变得模糊并且需要GHC扩展.我强烈建议阅读此博客文章，然后再进行设置在Haskell代码中使用存在性类型.

I read William Cook's "On Data Abstraction, Revisited", and re-read Ralf Laemmel's "The expression lemma" to try to understand how to apply the former paper's ideas in Haskell. So, I'm trying to understand how could you implement, e.g., a set union function, in Haskell without specifying the types?

解决方案

There's multiple ways, depending on which version of "abstract data types" you're after.

• Concrete but opaque types: It's been a little while since I read Cook's lovely paper, but glancing back over it I think this is closest to what he's talking about as ADTs. The standard way to do this in Haskell is to export a type without its constructors; what this means in Haskell:

  • No pattern matching on values of the abstracted type

  • No constructing values of the type, except using functions exported from its module

  How this relates to Cook's paper:

  • Representation independence: From the outside, the representation is inaccessible.

  • Inspection of multiple representations: Inside the ADT's module, representations may be inspected freely.

  • Unique implementations/modules: Different implementations can be provided by different modules, but the types cannot interoperate except by normal means. You can't use Data.IntMap.null to see whether a Data.Map.Map Int a is empty.

  This technique is used extensively in the Haskell standard libraries, particularly for data types that need to maintain some sort of invariant or otherwise restrict the ability to construct values. So in this case, the best way to implement the set ADT from the paper is the following code:

  import qualified Data.Set as S
  

  Although this is perhaps not as powerful a means of abstraction as it could be in a language with a more expressive module system.

• Existential quantification and interface: Haskell doesn't actually have an exists keyword as such, but the term "existential" is used in various circumstances to describe certain kinds of polymorphic types. The general idea in each case is to combine a value with a collection of functions operating on it, such that the result is polymorphic in the value's type. Consider this function signature:

  foo :: (a, a -> Bool) -> Bool
  

  Although it receives a value of type a, because a is fully polymorphic the only thing it can possibly do with that value is apply the function to it. So in a sense, within this function, the first half of the tuple is an "abstract data type", while the second half is an "interface" for working with that type. We can make this idea explicit, and apply it outside a single function, using an existential data type:

  data FooADT = forall a. FooADT a (a -> Bool)
  
  foo :: FooADT -> Bool
  

  Now, any time we have a value of type FooADT, all we know is that there exists some type a such that we can apply FooADT's second argument to its first.

  The same idea applies to polymorphic types with class constraints; the only difference is that the functions operating on the type are provided implicitly by the type class, rather than explicitly bundled with the value.

  Now, what does this mean in terms of Cook's paper?

  • Representation independence still applies.

  • Total isolation: Unlike before, knowledge of the existentially quantified type is forever lost. Nothing can inspect the representation except the interface it itself provides.

  • Arbitrary implementations: Not only are implementations not necessarily unique, there's no way to limit them at all! Anything that can provide the same interface can be wrapped up inside an existential and be indistinguishable from other values.

  In short, this is very similar to Cook's description of objects. For more on existential ADTs, the paper Unfolding Abstract Datatypes isn't a bad place to start; but keep in mind that what it discusses is fundamentally not what Cook is calling an ADT.

---

And a short addendum: Having gone to all the trouble above to describe existential type abstractions, I'd like to highlight something about the FooADT type: Because all you can do with it is apply the function to get a Bool result, there is fundamentally no difference between FooADT and Bool, except that the former obfuscates your code and requires GHC extensions. I strongly encourage reading this blog post before setting out to use existential types in Haskell code.

这篇关于如何在Haskell中声明抽象数据容器类型?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！