Pet*_*lák 12 haskell functional-programming pattern-matching data-structures
在函数式语言中设计数据结构时,有两种选择:
在什么情况下,什么是合适的？
模式匹配可以使代码更易读或更简单.另一方面,如果我们需要在数据类型的定义中更改某些内容,则需要更新我们在其上进行模式匹配(或构造它们)的所有位置.
我一直在问这个问题一段时间.通常我会发现我从一个简单的数据结构(甚至type别名)开始,似乎构造函数+模式匹配将是最简单的方法,并产生一个干净和可读的代码.但后来事情变得更复杂,我必须改变数据类型定义并重构代码的很大一部分.
mac*_*ron 10
对我来说,关键因素是以下问题的答案:
我的数据类型的结构是否与外界相关？
例如,列表数据类型的内部结构是非常相关的外部世界 - 它有一个感性的结构,肯定是要暴露给消费者非常有用的,因为他们构建进行感应的列表中的结构功能.如果列表是有限的,则保证这些函数终止.此外,以这种方式定义函数使得通过归纳再次提供关于它们的属性变得容易.
相比之下,最好将Set数据类型保持为抽象.在内部,它被实现为containers包中的树.然而,它也可能已经使用数组,或者(更有效地在功能设置)与一棵树,一个稍微不同的结构和尊重不同的不变量(平衡或不平衡,分支因子等)来实现.顺便说一下,需要在构造函数已经通过其类型实施的那些上面和上面强制执行任何不变量,从而排除让数据类型具体化.
列表示例和设置示例之间的本质区别在于Set数据类型仅与可能的操作相关Set.虽然列表是相关的,因为标准库已经提供了许多功能来对它们起作用,但另外它们的结构是相关的.
作为旁注,人们可能会反对实际上列表的归纳结构,这对于编写其终止和行为易于推理的函数非常重要,由两个消耗列表的函数抽象地捕获:foldr和foldl.鉴于这两个基本列表运算符,大多数函数根本不需要检查列表的结构,因此可以认为列表也可以保持抽象.这个论点可以推广到其他许多类似的结构,比如所有Traversable的结构,所有的Foldable结构等.然而,这是几乎不可能捕捉上列出了所有可能的递归模式,实际上很多功能不是递归的.只考虑foldr并且foldl,有人会写head,例如仍然可能,尽管很乏味:
head xs = fromJust $ foldl (\b x -> maybe (Just x) Just b) Nothing xs
只是放弃列表的内部结构我们会好得多.
最后一点是,有时数据类型的实际表示与外部世界无关,因为它说它是某种优化的,可能不是规范表示,或者没有单一的"规范"表示.在这些情况下,您需要保持数据类型为abstract,但提供数据类型的"视图",这些视图提供了可以进行模式匹配的具体表示.
一个例子是,如果想要定义Complex复数的数据类型,其中笛卡尔形式和极坐标形式都可以被认为是规范的.在这种情况下,您将保持Complex抽象,但导出两个视图,即函数,polar并分别cartesian返回笛卡尔平面中的一对长度和角度或坐标.
小智 7
嗯,规则很简单:如果通过使用实际的构造函数很容易构造错误的值,那么不要让它们直接使用,而是提供智能构造函数.这是一些像Map和的数据结构所遵循的路径Set,这很容易出错.
然后有些类型不可能或很难构造不一致/错误的值,因为类型根本不允许或者因为你需要引入底部.长度索引列表类型(通常称为Vec)和大多数monad是其中的示例.
最终这是你自己的决定.将自己置于用户的角度,并在便利性和安全性之间进行权衡.如果没有权衡,那么总是暴露构造函数.否则你的图书馆用户会讨厌你不必要的不透明度.
如果数据类型用于简单目的(如Maybe a),并且没有(显式或隐式)通过数据构造函数直接构造值可以违反关于数据类型的假设,我将公开构造函数.
另一方面,如果数据类型更复杂(如平衡树)和/或它的内部表示可能会改变,我通常会隐藏构造函数.使用软件包时,有一条不成文的规则,即非内部模块公开的接口应该在给定的数据类型上"安全"使用.考虑到平衡树示例,公开数据构造函数允许(意外地)构造不平衡树,因此可能违反搜索树等的假设运行时保证.
如果该类型用于表示具有规范定义和表示的值（许多数学对象属于此类），并且不可能使用该类型构造“无效”值，那么您应该公开构造函数。
例如，如果您用自己的类型（包括新类型）表示二维点之类的东西，您也可以公开构造函数。现实情况是，对此数据类型的更改不会改变 2d 点的表示方式，而是会改变您使用 2d 点的需求（也许您正在推广到 3d 空间，也许您是添加层的概念或其他），并且几乎肯定需要注意使用这种类型的值的代码部分，无论您做什么。[1]
表示特定于您的应用程序或领域的事物的复杂类型很可能会在继续支持类似操作的同时对表示进行更改。因此，您只需要取决于操作的其他模块，而不是内部结构。所以你不应该公开构造函数。
其他类型表示具有规范定义但不规范表示的事物。每个人都知道映射和集合所期望的属性，但是有许多不同的方式来表示支持这些属性的值。因此，您再次只需要其他模块，具体取决于它们支持的操作，而不是特定的表示。
某些类型，无论它们是否具有规范表示形式，都允许在程序中构造不表示该类型应该表示的抽象概念中的有效值的值。一个简单的例子是表示自平衡二叉搜索树的类型；可以访问构造函数的客户端代码可以轻松构造无效的树。公开构造函数要么意味着您需要假设从外部传入的此类值可能是无效的，因此即使对于奇怪的值，您也需要做出一些明智的事情，要么意味着使用您的接口的程序员有责任确保他们不这样做不违反任何假设。通常最好不要直接在模块外部构造此类类型。
基本上，这取决于您的类型应该代表的概念。如果您的概念以非常简单和明显的[2]方式直接映射到某些数据类型中的值，由于编译器无法检查所需的不变量，因此该概念并不比概念“更具包容性”，那么该概念几乎是“与数据类型相同”，并且公开其结构就可以了。如果没有，那么您可能需要隐藏该结构。
[1] 不过，一个可能的更改是更改用于坐标值的数字类型，因此您可能必须考虑如何最大程度地减少此类更改的影响。但这与您是否公开构造函数非常正交。
[2] 这里的“显而易见”意味着，如果您独立地要求 10 个人想出一个代表概念的数据类型，他们都会返回相同的结果，并对名称进行取模。