如何在Haskell中声明抽象数据容器类型？

我读过威廉库克的“关于数据抽象，重访”，并重新阅读拉尔夫拉梅尔的“表达式引理”，试图理解如何将前一篇文章的想法应用于哈斯克尔。所以，我试图理解如何在Haskell中实现，例如集合函数，而不指定类型？如何在Haskell中声明抽象数据容器类型？

来源

2010-06-30 BMeph

通过类型类，允许您模板函数，并替代数据类型和函数？ – 2010-06-30 22:43:09

有多种方式，这取决于“抽象数据类型”的版本，你是后。

混凝土，但不透明类型：这是一个小而自从我读库克的可爱的纸，但回头的时候了它，我觉得这是最接近于他在谈论的抽象数据类型。在Haskell中执行此操作的标准方法是在不使用构造函数的情况下导出类型;这意味着什么在Haskell：
- 无图案的抽象类型
- 类型的无构建值的值匹配，但用得自其模块导出的函数
这怎么涉及库克的纸：
- 表示独立性：从外部看，表示无法访问。
- 检查多个表示法：在ADT的模块内部，表示法可以自由检查。
- 独特的实现/模块：不同的实现可以由不同的模块提供，但除了通常的方式外，类型不能互操作。您不能使用Data.IntMap.null来查看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的第二个参数应用到它的第一个参数。

同样的想法适用于具有类约束的多态类型;唯一的区别是在类型上运行的函数是由类型类隐式提供的，而不是与值明确捆绑在一起。

现在，这对Cook的论文意味着什么？
- 表示独立性仍然适用。
- 完全隔离：与以前不同，对存在量化类型的了解永远丢失。除了它自己提供的接口外，没有什么可以检查表示。
- 任意实现：不仅实现不一定是唯一的，也没有办法限制它们！任何可以提供相同接口的东西都可以包含在存在中，并且与其他值无法区分。
总之，这与库克对物体的描述非常相似。有关存在性ADT的更多信息，论文Unfolding Abstract Datatypes并不是一个不错的开始;但请记住，它所讨论的内容根本不是Cook所称的ADT。

和短编：在经历上述所有的麻烦来形容生存型的抽象，我想强调一些有关FooADT类型：因为你可以用它做的应用函数得到一个Bool的结果，有从根本上没有区别FooADT和Bool，除了前者混淆你的代码，需要GHC扩展。在强制使用Haskell代码中的存在类型之前，我强烈建议reading this blog post。

来源

2010-07-01 01:23:51

谢谢你，camccann，这是一个杰出的答案 - 彻底，有见地，发人深思。（另外，我已经在luqui的博客上至少读了三次......仍然试图让它沉入其中。） – BMeph 2010-07-01 16:43:46

您可以要求提供比较函数或要求类型是等式的实例。这种技术的例子见nub和nubBy：

nub :: (Eq a) => [a] -> [a] 
nubBy :: (a -> a -> Bool) -> [a] -> [a]

来源

2010-06-30 22:59:39 Chuck

如何在Haskell中声明抽象数据容器类型？

回答

相关问题